Función recursiva que causa un desbordamiento de la pila

Question

Estoy tratando de escribir una función de criba simple para calcular los números primos en clojure. He visto this pregunta acerca de cómo escribir una función de tamiz eficiente, pero todavía no estoy en ese punto. En este momento solo intento escribir un tamiz muy simple (y lento). Esto es lo que he llegado con:

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

Para los pequeños rangos funciona bien, pero provoca un desbordamiento de pila para grandes gamas:

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) 

pensé que mediante el uso recur esto sería un no -construcción de bucle de consumo de pila? ¿Qué me estoy perdiendo?

Answer 1

Estás siendo golpeado por la pereza de filter. Cambie (filter ...) a (doall (filter ...)) en su formulario recur y el problema debería desaparecer.

A más explicación en profundidad:

La llamada a filter devuelve una SEC perezoso, que se materializa elementos reales de la SEC filtrada como se requiera. Como está escrito, su código apila filter al filter al filter ..., agregando un nivel más de filter ing en cada iteración; en algún momento esto explota. La solución es forzar el resultado completo en cada iteración para que el siguiente haga su filtrado en un seq completamente realizado y devuelva un seq completamente realizado en lugar de agregar una capa extra de procesamiento de seq perezoso; eso es lo que hace doall.

Answer 2

Algorítmicamente, el problema es que continúa filtrando cuando ya no tiene más propósito. Detener lo antes posible logra reducción cuadrática en profundidad de recursión (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)) 

ejecuta OK para 16000 (realizando sólo 30 iteraciones en lugar de 1862), y para 160.000 también, on ideone. Incluso se ejecuta un 5% más rápido sin el doall.