Clojure Lazy Sequences that Vectors

Question

He notado que las secuencias diferidas en Clojure parecen estar representadas internamente como listas enlazadas (o al menos están siendo tratadas como una secuencia con solo acceso secuencial a los elementos). Incluso después de haber sido guardado en la memoria caché, el tiempo de acceso sobre el Lazy-Seq con nth es O (n), no el tiempo constante como con los vectores.

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

¿Cómo puedo obtener una búsquedas en tiempo constante o crear un vector perezoso de forma incremental en Clojure?

Imagine que durante la generación del vector diferido, cada elemento es una función de todos los elementos anteriores a él, por lo que el tiempo dedicado a atravesar la lista se convierte en un factor importante.

preguntas relacionadas únicamente se presentaron esta incompleta fragmento de código Java: Designing a lazy vector: problem with const

Answer 1

Sí, secuencias en Clojure se describen como "logical lists" con tres operaciones (primero, después y contras).

Una secuencia es esencialmente la versión de Clojure de un iterador (aunque clojure.org insiste en que las secuencias no son iteradores, ya que no mantienen su estado original), y solo puede moverse a través de la colección de respaldo en un frente lineal fin de moda.

Los vectores vagos no existen, al menos no en Clojure.

Si desea búsquedas constantes en un rango de índices, sin calcular los elementos intermedios que no necesita, puede usar una función que calcula el resultado sobre la marcha. En combinación con la memorización (o el almacenamiento en caché de los resultados en un hash arg-to-result por su cuenta) obtiene prácticamente el mismo efecto que supongo que desea del vector perezoso.

Obviamente, esto solo funciona cuando hay algoritmos que pueden calcular f (n) más directamente que pasar por todos los precedentes f (0) ... f (n-1). Si no existe tal algoritmo, cuando el resultado para cada elemento depende del resultado para cada elemento anterior, no se puede hacer mejor que el iterador de secuencia en cualquier caso.

Editar

Por cierto, si lo que quieres es para que el resultado sea un vector para que pueda obtener las búsquedas rápidas después, y no le importa que los elementos se crean de forma secuencial la primera vez, eso es bastante simple .

Aquí es una aplicación de Fibonacci utilizando un vector:

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

Aquí estamos usando una secuencia perezoso para posponer la función de llamada hasta que pidieron (iterate devuelve una secuencia perezoso), pero los resultados son recogidos y devueltos en un vector.

El vector crece según sea necesario, agregamos solo los elementos hasta el último pedido, y una vez calculado se trata de una búsqueda de tiempo constante.

¿Era algo así como lo que tenía en mente?