Clojure Lazy secuencias que son vectores

Question

he dado cuenta de que las secuencias de descanso bajo Clojure parecen estar representados internamente como listas enlazadas (o al menos que se les trata como una secuencia con sólo el acceso secuencial a los elementos). Incluso después de haber sido almacenado en caché en la memoria, el tiempo de acceso sobre el perezoso-seq con nth es O (n), no constante de tiempo como con 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 llego a las búsquedas en tiempo constante o crear un vector perezoso de forma incremental en Clojure?

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

preguntas relacionadas únicamente se presentó esta incompleta fragmento Java: El diseño de un vector perezoso: anomalía en la const

Answer 1

Sí, secuencias en Clojure se describen como "listas lógicas" con tres operaciones (primero, siguiente y los contras) .

Una secuencia es esencialmente la versión Clojure de un iterador (aunque clojure.org insiste en que las secuencias no son iteradores, ya que no se sostienen estado iternal), y sólo puede moverse a través de la colección de respaldo en un lineal de adelante hacia final de la moda.

no existen vectores

perezoso, al menos no en Clojure.

Si desea que las búsquedas de tiempo constantes sobre una gama de índices, sin calcular elementos intermedios que no es necesario, se puede utilizar una función que calcula el resultado sobre la marcha. Combinado con memoization (o almacenamiento en caché de los resultados en un hash-Arg-a consecuencia de su propia) se obtiene prácticamente el mismo efecto que supongo que desee en el vector de perezoso.

Obviamente, esto sólo funciona cuando hay algoritmos que pueden calcular f (n) más directamente que pasar por todo f precedente (0) ... f (n-1). Si no existe tal algoritmo, cuando el resultado de cada elemento depende del resultado para cada elemento anterior, no se puede hacer mejor que el iterador 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, que es lo suficientemente simple.

Esta 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 las llamadas a funciones hasta que pidieron (retornos iterate una secuencia perezosa), pero los resultados se recogen y se devuelven en un vector.

El vector crece a medida que sea necesario, se añade sólo los elementos hasta el último pedido, y una vez computada es una búsqueda constante de tiempo.

¿Era algo como esto se tuvo en cuenta?