Clojure - coda setaccio ricorsiva di Eratostene

Ho questa implementazione del crivello di Eratostene in Clojure:Clojure - coda setaccio ricorsiva di Eratostene

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

Per maggiore n (come 20000) termina con overflow dello stack. Perché qui non funziona l'eliminazione chiamata coda? Come sistemarlo?

fonte

2010-06-05 Konrad Garus

Come nota a margine, ma questo non è il setaccio di Eratostene. SoE non esegue operazioni di resto, solo aggiunte e "crossing out". Vedi http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf per una discussione estesa (è un'ottima lettura!); per una bella implementazione SoE "incrementale" in Clojure di Christophe Grand, vedi http://clj-me.cgrand.net/2009/07/30/everybody-loves-the-sieve-of-eratosthenes/ (è anche il più veloce versione che ho visto finora). –

@ Michał Marczyk ringrazia. Direi che "crossing out" equivale a "filtering" e "addizione" in questo algoritmo equivale a "moltiplicazione" e di conseguenza "resto". –

Non proprio. Il risultato è, ovviamente, lo stesso, ma la complessità algoritmica è molto diversa. –

Problema: filter esegue una valutazione lenta, quindi ogni nuovo livello di filtro si blocca sullo stack delle chiamate.

Correzione: modifica (filter ...) a (doall (filter ...)).

Vedere la spiegazione here.

fonte

2010-06-05 14:05:56

Se si guarda al backtrace

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

Sembra che questo:

... 
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) 
...

E 'troppi filtri che sta causando il troppo pieno, non il ciclo.

Sfortunatamente, non vedo una soluzione ovvia per questo.

fonte

2010-06-05 13:55:02 cobbal

L'indizio era nel LazySeq. L'implementazione di Clojures di Pigrizia ha alcuni trucchi, essendo questo uno di loro. –

hai identificato correttamente il problema algoritmico principale (al contrario di solo tecnico). una soluzione ovvia è smettere di filtrare non appena non c'è più bisogno di filtrare. e cioè, quando '(> (* last-tried last-tried) n)'. Per 20000, significa trading profondità di ricorsione di circa 2000, per circa 30. –

(in effetti [per 16.000] (http://stackoverflow.com/a/41621006/849891) è 30 contro 1862 filtri nidificati). –

I secondo commento di Michal Marczyk sulla verifica del bellissimo SoE incrementale di cgrande. Ho fatto alcuni benchmark davvero primitivi e li ho montati allo http://clojure.roboloco.net/?p=100, per coloro che sono curiosi delle prestazioni del generatore di prime pigre.

fonte

2010-06-09 03:16:34 ivar

Clojure - coda setaccio ricorsiva di Eratostene

risposta

Problemi correlati