Clojure - tail rekursiven Sieb von Eratosthenes

Ich habe diese Umsetzung des Siebes von Eratosthenes in Clojure:Clojure - tail rekursiven Sieb von Eratosthenes

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

Für größere n (wie 20000) endet mit Stapelüberlauf. Warum funktioniert die Tail Call Elimination hier nicht? Wie man es repariert?

Quelle

2010-06-05 Konrad Garus

Als eine Randnotiz, aber das ist nicht das Sieb von Eratosthenes. SoE führt keine Restoperationen durch, nur Addition und "Durchstreichen". Siehe http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf für eine ausführliche Diskussion (es ist eine tolle Lektüre!); Für eine schöne "inkrementelle" SoE-Implementierung in Clojure von Christophe Grand, siehe http://clj-me.cgrand.net/2009/07/30/everybody-loves-the-sieve-of-eratosthenes/ (es ist auch die schnellste Version, die ich bisher gesehen habe). –

@ Michał Marczyk danke. Ich würde sagen, dass "crossing out" äquivalent zu "filtering" ist, und "addition" in diesem Algorithmus ist gleichbedeutend mit "multiplication" und folglich "rest". –

Nicht wirklich. Das Ergebnis ist natürlich dasselbe, aber die algorithmische Komplexität ist sehr unterschiedlich. –

Problem: filter macht faule Auswertung, so hängt jede neue Ebene der Filterung auf dem Call-Stack herum.

Fix: Ändern (filter ...) zu (doall (filter ...)).

Siehe die Erklärung here.

Quelle

2010-06-05 14:05:56

Wenn man sich die Backtrace sehen

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

es sieht wie folgt aus:

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

Es ist zu viele Filter, die den Überlauf verursacht, nicht die Schleife.

Leider sehe ich keine offensichtliche Lösung dafür.

Quelle

2010-06-05 13:55:02 cobbal

Der Hinweis war in der LazySeq. Clojures Implementierung von Faulheit hat ein paar Fehler, dies ist einer von ihnen. –

Sie haben das algorithmische Hauptproblem richtig erkannt (im Gegensatz zu nur technisch). Eine naheliegende Lösung besteht darin, die Filterung zu stoppen, sobald keine Filterung mehr erforderlich ist. und das ist, wenn '(> (zuletzt versucht-zuletzt versucht) n)'. Für 20000 bedeutet das eine Rekursionstiefe von ungefähr 2000, für nur ungefähr 30. –

(tatsächlich [für 16.000] (http://stackoverflow.com/a/41621006/849891) sind es 30 vs 1862 verschachtelte Filter). –

Ich bin der zweite Kommentar von Michal Marczyk zum Auschecken der schönen inkrementellen SoE von cgrande. Ich habe einige wirklich primitive Benchmarks gemacht und sie auf http://clojure.roboloco.net/?p=100 gesetzt, für diejenigen, die neugierig auf die Leistung von Lazy-Prime-Generatoren sind.

Quelle

2010-06-09 03:16:34 ivar

Clojure - tail rekursiven Sieb von Eratosthenes

Antwort

Verwandte Themen