Quelle est la meilleure technique pour générer de manière paresseuse une structure de données à accès aléatoire ?

Question

En Haskell, j'aimerais générer une liste d'entiers aléatoires de longueur indéterminée. (Cependant, inférieure à disons 1 million.)

Il est peu probable que j'aie besoin immédiatement de tous les éléments de la liste, donc j'aimerais la générer de manière paresseuse. Cependant, une fois générée, j'aurai besoin d'accéder aux éléments de la liste de manière aléatoire. Donc, je suppose que la meilleure technique serait de copier une liste infinie dans un tableau. Cependant, je ne sais pas si les tableaux peuvent être "interchangeables" avec les listes très facilement - par exemple, une fois que je veux générer plus d'éléments de la liste, je veux reprendre là où je me suis arrêté mais agrandir le tableau.

De toute façon, peut-être devrais-je me contenter d'une structure d'arbre en log(n) au lieu d'un tableau? Qu'en penses-tu?

Est-ce que Haskell a une structure d'arbre pour les éléments séquentiels qui peut être accédée en utilisant une interface de type liste?

Answer 1

Si vous avez un bon générateur de nombres pseudo-aléatoires, alors les valeurs générées avec des graines proches devraient être indépendantes, donc vous pouvez simplement choisir une graine initiale, puis chaque cellule i dans le tableau sera prng(seed+i).

C'est essentiellement juste l'utiliser comme une fonction de hachage :P

Si vous le faites de cette manière, vous n'avez même pas vraiment besoin du tableau, vous pouvez simplement avoir une fonction getRandomValue seed i = prng (seed+i). Que ce soit mieux ou pas qu'un tableau de valeurs paresseuses dépendra de la complexité de votre générateur de nombres pseudo-aléatoires, mais dans tous les cas, vous aurez un accès en O(1).

Answer 2

Cela semble être utile, mais vous auriez besoin de générer des arbres de plus en plus grands à mesure que la liste s'allonge: http://www.codeproject.com/KB/recipes/persistentdatastructures.aspx#RandomAccessLists (c'est une structure de l'ordre de log(n), cependant). Quelque chose comme http://research.janelia.org/myers/Papers/applicative.stack.pdf pourrait également être utile, mais je ne vois pas immédiatement comment le faire fonctionner efficacement (avec une structure partagée) lorsque la liste est générée dynamiquement.

Une approche possible serait d'utiliser un générateur de nombres pseudo-aléatoires qui permet de "sauter", ou de passer en avant n étapes en un temps sublinéaire. Une méthode (qui est lente, mais fonctionne en temps constant) consiste à utiliser un chiffrement par bloc en mode compteur; voir http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator#Designs_based_on_cryptographic_primitives. Voir http://cs.berkeley.edu/~mhoemmen/cs194/Tutorials/prng.pdf pour plus d'informations.

Answer 3

Pas une réponse, mais une considération : notez que toute technique standard pour générer une liste de valeurs aléatoires impliquera un fil à travers une graine. Donc si je génère une liste infinie de nombres aléatoires paresseux et que je force la valeur du 100ème élément, cela force non seulement l'épine dorsale des cellules de cons 0-99 mais aussi leurs valeurs également.

De toute façon, je recommanderais des vecteurs stockables paresseux : http://hackage.haskell.org/package/storablevector

Vous avez toujours un accès O(n), mais vous l'avez réduit par le facteur de votre taille de bloc, donc en pratique c'est beaucoup plus rapide qu'une simple liste. Et vous obtenez toujours, modulo la taille du bloc, les propriétés de paresse que vous recherchez.

Answer 4

Que dire de Data.Sequence.Seq ? Ce n'est pas paresseux, mais il prend en charge des ajouts en O(1) à chaque extrémité, et les recherches sont en O(log(min(i,n-i))), ce qui devrait être mieux que la plupart des autres structures arborescentielles. Vous pourriez garder une Seq et générer/ajouter plus de sorties au besoin.

Il existe également une instance pour ListLike si vous préférez cette API à celle fournie par Seq.

Answer 5

Une chose que vous pourriez faire est de créer une liste de tableaux. Ainsi, si chaque tableau stocke M éléments de votre séquence, accéder à l'élément n est en O(n/M). Cela pourrait être un bon compromis.

Par exemple :

import Data.Array
import Data.List

fibsList :: (Num a) => [a]
fibsList = 1 : 1 : zipWith (+) fibsList (tail fibsList)

chunkSize :: (Num a, Ix a) => a
chunkSize = 100000

fibsChunks :: (Num i, Ix i, Num e) => [Array i e]
fibsChunks = mkChunks fibsList
  where mkChunks fs = listArray (0,chunkSize-1) xs : mkChunks ys
          where (xs,ys) = splitAt chunkSize fs

lookupFib :: (Integral i, Ix i, Num e) => i -> e
lookupFib n = fibsChunks `genericIndex` q ! r
  where (q,r) = n `divMod` chunkSize