Clojure Faule Sequenzen, die Vektoren sind

Question

Ich habe festgestellt, dass in Clojure lazy Sequenzen scheinen intern dargestellt zu werden als verknüpfte Listen (oder zumindest werden sie nur mit sequentiellem Zugriff auf Elemente als eine Sequenz behandelt werden). Auch nach in dem Speicher zwischengespeichert wird, die Zugriffszeit über den lazy-seq mit nth ist O (n), nicht konstant mit der Zeit als Vektoren.

;; ...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"

Wie erhalte ich eine konstante Zeit Lookups oder einen faulen Vektor schrittweise in Clojure erstellen?

Stellen Sie sich vor, dass bei der Erzeugung des faulen Vektor, jedes Element ist eine Funktion aller Elemente vorherigen ihn, so dass die Zeit, um die Liste ausgegeben überquert wird ein wichtiger Faktor.

Damit zusammenhängende Fragen aufgedreht nur diese unvollständig Java-Snippet: Entwerfen eines faulen Vektor: Problem mit konst

Answer 1

Ja, Sequenzen in Clojure werden beschrieben als „logische Listen“ mit drei Operationen (ersten, nächsten und Nachteile) .

Eine Sequenz ist im Wesentlichen die Clojure Version eines Iterators (obwohl clojure.org besteht darauf, dass Sequenzen, die nicht Iteratoren sind, da sie nicht iternal Zustand zu halten), und kann nur durch die Trägersammel bewegt sich in einem linearen Front-to- End-Mode.

Faule Vektoren existiert nicht, zumindest nicht in Clojure.

Wenn Sie möchten, konstante Zeit Lookups über einen Bereich von Indizes, ohne Zwischenelemente Berechnen Sie nicht benötigen, können Sie eine Funktion verwenden, die das Ergebnis im laufenden Betrieb berechnet. In Kombination mit memoization (oder Zwischenspeichern der Ergebnisse in einem arg-to-Ergebnis-Hash auf eigene Faust) Sie so ziemlich den gleichen Effekt, wie ich Sie von den faulen Vektor annehmen wollen.

Das funktioniert natürlich nur, wenn es Algorithmen, die f (n) mehr direkt als gehen durch alle vorhergehenden f (0), ... f (n-1) berechnen kann. Wenn es keinen solchen Algorithmus ist, wenn das Ergebnis für jedes Element für jedes vorherige Element auf das Ergebnis hängt, können Sie nicht besser als die Sequenz Iterator auf jeden Fall.

Bearbeiten

BTW, wenn alles, was Sie wollen, ist für das Ergebnis ein Vektor, so dass Sie danach schnell Lookups, und Sie nicht dagegen, dass Elemente der Reihe nach dem ersten Mal erstellt werden, die einfach genug.

Hier ist eine Fibonacci-Implementierung unter Verwendung eines Vektors:

(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]

Hier haben wir einen faulen Sequenz werden mit den Funktionsaufrufe zu verschieben, bis zum (iterate kehrt eine faule Sequenz) gefragt, aber die Ergebnisse werden gesammelt und in einem Vektor zurück.

Der Vektor wächst nach Bedarf, fügen wir die Elemente nur bis zum letzten up gefragt, und einmal berechnet, es ist eine konstante Zeit Lookup.

War es so etwas wie dieses Sie im Sinn hatte?