Rekursive Funktion verursacht einen Stapelüberlauf

Question

Ich versuche, eine einfache Siebfunktion zu schreiben, um Primzahlen in Clojure zu berechnen. Ich habe this Frage über das Schreiben einer effizienten Siebfunktion gesehen, aber ich bin zu diesem Punkt noch nicht. Im Moment versuche ich nur ein sehr einfaches (und langsames) Sieb zu schreiben. Hier ist, was ich habe kommen mit:

(defn sieve [potentials primes] 
    (if-let [p (first potentials)] 
    (recur (filter #(not= (mod % p) 0) potentials) (conj primes p)) 
    primes)) 

Für kleine Bereiche es funktioniert gut, aber verursacht einen Stapelüberlauf für große Bereiche:

user=> (sieve (range 2 30) []) 
[2 3 5 7 11 13 17 19 23 29] 
user=> (sieve (range 2 15000) []) 
java.lang.StackOverflowError (NO_SOURCE_FILE:0) 

Ich dachte, dass recur unter Verwendung dieses ein nicht wäre -stackverzehrendes Looping-Konstrukt? Was vermisse ich?

Answer 1

Sie werden von filter Faulheit getroffen. Ändern Sie (filter ...) zu (doall (filter ...)) in Ihrem recur Formular und das Problem sollte weggehen.

Eine weitergehende Erklärung:

Der Aufruf von filter gibt einen lazy seq, die nach Bedarf tatsächlichen Elemente des gefilterten seq materialisiert. Wie beschrieben, stapelt Ihr Code filter auf filter auf filter ..., Hinzufügen einer weiteren Ebene von filter in jeder Iteration; Irgendwann explodiert das. Die Lösung besteht darin, das gesamte Ergebnis bei jeder Iteration zu erzwingen, so dass das nächste seine Filterung auf einer vollständig realisierten Sequenz durchführt und eine vollständig realisierte Sequenz zurückgibt, anstatt eine zusätzliche Schicht von Lazy-Seq-Verarbeitung hinzuzufügen; das ist was doall tut.

Answer 2

Algorithmisch besteht das Problem darin, dass Sie weiter filtern, wenn es keinen Zweck mehr dafür gibt. so früh wie möglich zu stoppen erreicht quadratische Reduktion der Rekursionstiefe (sqrt(n) vs. n):

(defn sieve [potentials primes]  
    (if-let [p (first potentials)] 
     (if (> (* p p) (last potentials)) 
     (concat primes potentials) 
     (recur (filter (fn [n] (not= (mod n p) 0)) potentials) 
       (conj primes p))) 
    primes)) 

Läuft OK für 16.000 (performing nur 30 Iterationen statt 1862) und für 160.000 zu, on ideone. Sogar läuft 5% schneller ohne die .