Clojure qui sont paresseux séquences vecteurs

Question

nous avons remarqué que les séquences paresseux à Clojure semblent être représenté en interne en tant que listes liées (ou au moins ils sont traités en tant que séquence avec seulement un accès séquentiel à des éléments). Même après avoir été mis en cache dans la mémoire, le temps d'accès sur-seq paresseux avec nth est O (n), non constante de temps avec des vecteurs.

;; ...created my-lazy-seq here and used the first 50,000 items

(time (nth my-lazy-seq 10000))
"Elapsed time: 1.081325 msecs"

(time (nth my-lazy-seq 20000))
"Elapsed time: 2.554563 msecs"

Comment puis-je obtenir un temps de lookups constante ou créer un vecteur paresseux progressivement dans Clojure?

Imaginons que lors de la génération du vecteur paresseux, chaque élément est une fonction de tous les éléments précédents à elle, de sorte que le temps passé à parcourir la liste devient un facteur important.

Questions connexes ne relevai cette incomplète snippet Java: Concevoir un vecteur paresseux: problème avec const

Answer 1

Oui, séquences dans Clojure sont décrits comme « listes logiques » avec trois opérations (en premier lieu, à côté et le contre) .

Une séquence est essentiellement la version Clojure d'un itérateur (bien que clojure.org insiste que les séquences ne sont pas itérateurs, car ils ne tiennent pas état iternal), et ne peut se déplacer dans les collections de support dans une face-to-linéaire mode fin.

vecteurs paresseux n'existent pas, du moins pas dans Clojure.

Si vous voulez temps constant des recherches sur une gamme d'indices, sans calcul des éléments intermédiaires vous n'avez pas besoin, vous pouvez utiliser une fonction qui calcule le résultat à la volée. Combiné avec memoization (ou la mise en cache des résultats dans un hachage arg à résultat sur votre propre) vous obtenez à peu près le même effet que je suppose que vous voulez à partir du vecteur paresseux.

Cela fonctionne évidemment que lorsqu'il y a des algorithmes qui peuvent calculer f (n) plus directement que de passer par tous les f précédentes (0) ... f (n-1). S'il n'y a pas tel algorithme, lorsque le résultat pour chaque élément dépend du résultat pour chaque élément précédent, vous ne pouvez pas faire mieux que la séquence iterator dans tous les cas.

Modifier

BTW, si vous voulez tout est le résultat d'être un vecteur de sorte que vous obtenez rapidement après les recherches, et ne vous dérange pas que les éléments sont créés successivement la première fois, c'est assez simple.

Voici une implémentation de Fibonacci en utilisant un vecteur:

(defn vector-fib [v]
  (let [a (v (- (count v) 2)) ; next-to-last element
        b (peek v)]   ; last element
    (conj v (+ a b))))

(def fib (iterate vector-fib [1 1]))

(first (drop 10 fib))
  => [1 1 2 3 5 8 13 21 34 55 89 144]

Ici, nous utilisons une séquence paresseux pour reporter les appels de fonction jusqu'à ce que demandé (retourne iterate une séquence paresseux), mais les résultats sont collectés et renvoyés dans un vecteur.

Le vecteur croît en fonction des besoins, on ajoute que les éléments jusqu'à la dernière a demandé, et une fois calculé, il est une recherche de temps constant.

Était-ce quelque chose comme ça vous aviez à l'esprit?