Pregunta para principiantes sobre el montón y la basura en Clojure

Question

Tengo una pregunta sobre Clojure: Estoy tratando de aprender el idioma yendo a través de Project Euler y no entiendo lo que está pasando debajo del capó: El siguiente código está diseñado para use return una lista de todos los números primos hasta lim. Creo que debería ser O (n) en el espacio dinámico porque hago una lista de todos los números hasta lim, y luego los filtro uno por uno mientras muevo el primero a una nueva lista. (Yo sé que en realidad estoy haciendo nuevas listas de cada reaparecer, pero no pensé que tomarían más memoria?) De todas formas estoy funcionando con este

(defn getAllPrimes [lim] 
    (defn getPrimes [primes numlist] 
    (if (not-empty numlist) ;base case; 
    (recur (cons (first numlist) primes) ;put the prime on to the prime list 
      (filter 
     (fn [x] (not (div? x (first numlist)))) ;remove the prime and all its multiples from the numlist 
     (rest numlist))) 
     primes)); return the primes 
    (getPrimes() (range 2 lim))) ;call the recursive function with and empty prime list to be filled up and a full numlist to be emptied 

Y sigo quedando sin espacio de almacenamiento dinámico, cuando llamo

(apply + (getAllPrimes 2000000)) 

, pero no me quedo sin espacio en

(apply + (filter even? (range 2000000))) 

Así que creo que no debo entender cómo están las listas de basura recogidas en las llamadas que se repita y en realidad estoy usando O (n * n) montón o algo.

Answer 1

Creo que el problema es que con cada repetición, estás creando una nueva secuencia diferida en referencia a la última, por lo que después de algunas iteraciones tienes una secuencia que contiene el encabezado de una secuencia que contiene la cabeza de un seq que tiene la cabeza de una seq. ... Todos los seqs intermedios están llenando tu montón.

Aunque escribir un tamiz prime es un ejercicio que vale la pena, si quieres llegar a la respuesta, Clojure incluye la secuencia de números primos en su biblioteca estándar: clojure.contrib.lazy-seqs/primes. La solución estándar para este problema de Euler paricular es de una sola línea.

Como punto de estilo, un defn interno no es una buena idea. El efecto práctico es el mismo que si defn estuvieran en el nivel superior, pero si no me equivoco, la var se reasigna cada vez que se llama a getAllPrimes, y se desaconseja la redefinición de vars en el tiempo de ejecución. Como el código solo define una var, getPrimes sigue siendo tan visible como getAllPrimes. En este caso, getPrimes podría reescribirse fácilmente como un bucle/recurrencia sin función interna, anónima o nombrada. Eso no ayuda a su cadena de lazy-SEQs problema, pero hace que el código un poco más de aspecto estándar:

(defn getAllPrimes [lim] 
    (loop [primes() 
     numlist (range 2 lim)] 
    (if (not-empty numlist) 
     (recur (cons (first numlist) primes) 
      (filter (fn [x] (not (div? x (first numlist)))) 
        (rest numlist))) 
     primes))) 

Me gustaría también evitar el uso de camelCase. El nombre estándar de Clojure para esta función sería get-all-primes.

Volviendo al problema práctico, sin embargo, el mínimo trabajo que podría hacer para que su código funcione sería forzar cada secuencia en cada iteración, es decir, envolver su llamada de filtro en una doall. He intentado esto, y si bien aún se ejecuta lentamente, por lo menos se ejecuta hasta su finalización sin el funcionamiento del montón:

(defn get-all-primes [lim] 
    (loop [primes() 
     numlist (range 2 lim)] 
    (if (not-empty numlist) 
     (recur (cons (first numlist) primes) 
      (doall (filter #(not (div? % (first numlist))) 
          (rest numlist)))) 
     primes)))