Clojure: ¿Cómo evitar el desbordamiento de pila en Sieve of Erathosthene?

primes tail-recursion

Question

Aquí está mi implementación de Sieve of Erathosthene en Clojure (basada en la lección de SICP sobre transmisiones):

(defn nats-from [n]
  (iterate inc n))

(defn divide? [p q]
  (zero? (rem q p)))

(defn sieve [stream]
  (lazy-seq (cons (first stream)
            (sieve (remove #(divide? (first stream) %) 
               (rest stream))))))

(def primes (sieve (nats-from 2)))

Ahora, todo está bien cuando tomo los primeros 100 primos:

(take 100 primes)

Pero, si intento tomar los primeros 1000 primos , el programa se rompe debido al desbordamiento de la pila. Me pregunto si es posible cambiar de alguna manera el tamiz de función para volverse recursivo de cola y, aún así, preservar las "corrientes" de algoritmo.

¿¿¿Alguna ayuda???

Answer 1

En primer lugar, este no es el Tamiz de Eratóstenes ... ver mi comentario para más detalles.

En segundo lugar, me disculpo por el voto a puerta cerrada, ya que su pregunta no es un duplicado real de la que señalé ... Malo.

Explicación de lo que está sucediendo

La diferencia radica, por supuesto, en el hecho de que está tratando de construir un tamiz incremental , donde el rango sobre el que funciona la llamada de remove es infinito y, por lo tanto, es imposible envolverlo todo. La solución es implementar uno de los SoE incrementales "reales" del documento con el que parezco enlazar con bastante frecuencia estos días: The Genuine Sieve of Eratosthenes de Melissa E. O''Neill.

Christophe Grand ha escrito una implementación de criba Clojure particularmente hermosa y está disponible aquí para la admiración de todos los que puedan estar interesados. Lectura altamente recomendada

En cuanto a la fuente del problema, las preguntas que originalmente pensé que era tuya eran un duplicado de las explicaciones que deberían ser útiles para ti: mira aquí y aquí . Una vez más, perdón por el voto precipitado para cerrar.

Por qué la recursividad de cola no ayudará

Dado que la pregunta menciona específicamente hacer que la función de cribado sea recursiva como una posible solución, pensé que abordaría eso aquí: las funciones que transforman las secuencias perezosas no deberían, en general, ser recursivas de cola .

Este es un punto bastante importante a tener en cuenta y uno que hace tropezar a muchos programadores sin experiencia de Clojure (o Haskell). La razón es que una función recursiva de la cola de la necesidad solo devuelve su valor una vez que está "lista", al final del cálculo. (Un proceso iterativo puede, al final de cualquier iteración particular, devolver un valor o continuar a la siguiente iteración.) En constrast, una función que genera una secuencia perezosa debe devolver inmediatamente un objeto de secuencia perezosa que encapsula bits de código que se le puede pedir que produzca la cabeza o la cola de la secuencia siempre que lo desee.

Por lo tanto, la respuesta al problema de apilar transformaciones perezosas no es hacer que nada sea recursivo, sino fusionar las transformaciones. En este caso particular, se puede obtener el mejor rendimiento utilizando un esquema personalizado para fusionar las operaciones de filtrado, basadas en colas de prioridad o mapas (consulte el artículo mencionado anteriormente para obtener más información).