Clojure Sequenze pigre che sono vettori

Question

Ho notato che le sequenze pigre in Clojure sembrano essere rappresentate internamente come elenchi collegati (o almeno vengono trattate come una sequenza con solo accesso sequenziale agli elementi).Anche dopo essere stato memorizzato nella cache, accedere al tempo tramite lazy-seq con nth è O(n), non tempo costante come con i vettori.

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

Come posso ottenere ricerche in tempo costante o creare un vettore pigro in modo incrementale in Clojure?

Immagina che durante la generazione del vettore pigro, ogni elemento sia una funzione di tutti gli elementi precedenti, quindi il tempo impiegato per attraversare l'elenco diventa un fattore significativo.

Le domande correlate hanno mostrato solo questo snippet Java incompleto:Progettare un vettore pigro:problema con const

Answer 1

Sì, le sequenze in Clojure sono descritte come "elenchi logici" con tre operazioni (prima, successiva e contro).

Una sequenza è essenzialmente la versione Clojure di un iteratore (sebbene clojure.org insista sul fatto che le sequenze non sono iteratori, poiché non mantengono uno stato interno) e possono spostarsi solo attraverso la raccolta di supporto in modo lineare front-to-end.

I vettori pigri non esistono, almeno non a Clojure.

Se desideri ricerche temporali costanti su un intervallo di indici, senza calcolare gli elementi intermedi che non ti servono, puoi utilizzare una funzione che calcola il risultato al volo.In combinazione con la memoizzazione (o la memorizzazione nella cache dei risultati in un hash arg-risultato da solo) ottieni praticamente lo stesso effetto che presumo tu voglia dal vettore pigro.

Questo ovviamente funziona solo quando ci sono algoritmi in grado di calcolare f(n) in modo più diretto rispetto a tutti i precedenti f(0)...f(n-1).Se non esiste un algoritmo di questo tipo, quando il risultato di ogni elemento dipende dal risultato di ogni elemento precedente, in ogni caso non puoi fare di meglio dell'iteratore di sequenza.

Modificare

A proposito, se tutto ciò che desideri è che il risultato sia un vettore in modo da ottenere ricerche rapide in seguito e non ti dispiace che gli elementi vengano creati in sequenza la prima volta, è abbastanza semplice.

Ecco un'implementazione di Fibonacci che utilizza un vettore:

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

Qui stiamo usando una sequenza pigra per posticipare le chiamate di funzione finché non vengono richieste (iterate restituisce una sequenza pigra), ma i risultati vengono raccolti e restituiti in un vettore.

Il vettore cresce secondo necessità, aggiungiamo solo gli elementi fino all'ultimo richiesto, e una volta calcolato è una ricerca temporale costante.

Era qualcosa del genere che avevi in ​​mente?