Clojure - criba de Eratóstenes recursiva cola

que tiene esta aplicación de la criba de Eratóstenes en Clojure:Clojure - criba de Eratóstenes recursiva cola

(defn sieve [n] 
    (loop [last-tried 2 sift (range 2 (inc n))] 
    (if 
     (or (nil? last-tried) (> last-tried n)) 
     sift 
     (let [filtered (filter #(or (= % last-tried) (< 0 (rem % last-tried))) sift)] 
     (let [next-to-try (first (filter #(> % last-tried) filtered))] 
     (recur next-to-try filtered))))))

Para mayor n (como 20000) termina con desbordamiento de pila. ¿Por qué la cola no funciona aquí? ¿Como arreglarlo?

Fuente

2010-06-05 Konrad Garus

Como nota al margen, pero este no es el tamiz de Eratóstenes. SoE no realiza operaciones de resto, solo suma y "tachando". Vea http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf para una discusión extensa (¡es una gran lectura!); para una hermosa implementación de SoE "incremental" en Clojure por Christophe Grand, ver http://clj-me.cgrand.net/2009/07/30/everybody-loves-the-sieve-of-eratosthenes/ (también es el más rápido) versión que he visto hasta ahora). –

@ Michał Marczyk gracias. Yo diría que "tachar" es equivalente a "filtrado", y "adición" en este algoritmo es equivalente a "multiplicación" y, en consecuencia, "resto". –

No realmente. El resultado es, por supuesto, el mismo, pero la complejidad algorítmica es tremendamente diferente. –

Problema: filter realiza una evaluación diferida, por lo que cada nuevo nivel de filtrado se queda en la pila de llamadas.

Solución: cambie (filter ...) por (doall (filter ...)).

Ver la explicación here.

Fuente

2010-06-05 14:05:56

Si nos fijamos en la traza

(try 
(sieve 200000) 
(catch java.lang.StackOverflowError e 
    (.printStackTrace e)))

que se parece a esto:

... 
at clojure.lang.LazySeq.sval(LazySeq.java:42) 
at clojure.lang.LazySeq.seq(LazySeq.java:56) 
at clojure.lang.RT.seq(RT.java:440) 
at clojure.core$seq__4176.invoke(core.clj:103) 
at clojure.core$filter__5033$fn__5035.invoke(core.clj:1751) 
at clojure.lang.LazySeq.sval(LazySeq.java:42) 
at clojure.lang.LazySeq.seq(LazySeq.java:56) 
...

de que sea demasiado muchos filtros que está causando el desbordamiento, no el bucle.

Desafortunadamente, no veo una solución obvia para esto.

Fuente

2010-06-05 13:55:02 cobbal

La pista estaba en el LazySeq. La implementación de la pereza de Clojures tiene algunos inconvenientes, siendo esta una de ellas. –

ha identificado correctamente el problema algorítmico principal (en lugar de simplemente técnico). una solución obvia es dejar de filtrar tan pronto como ya no haya necesidad de filtrar. y es decir, cuando '(> (* last-tried last-tried) n)'. Para 20000, eso significa una profundidad de recursión comercial de aproximadamente 2000, para aproximadamente 30. –

(de hecho [para 16,000] (http://stackoverflow.com/a/41621006/849891) son filtros anidados 30 vs 1862). –

En segundo lugar, el comentario de Michal Marczyk sobre comprobar el hermoso SoE incremental de cgrande. Realicé algunos benchmarks realmente primitivos y los puse al http://clojure.roboloco.net/?p=100, para aquellos curiosos sobre el rendimiento del generador principal perezoso.

Fuente

2010-06-09 03:16:34 ivar

Clojure - criba de Eratóstenes recursiva cola

Respuesta

Cuestiones relacionadas