Domanda per principianti su heap e spazzatura in Clojure

Question

Ho una domanda su Clojure: Sto cercando di imparare la lingua passando attraverso Project Euler e non capisco cosa sta succedendo sotto il cofano: Il seguente codice è progettato per utilizzare restituire un elenco di tutti i numeri primi fino a lim. Penso che dovrebbe essere O (n) nello spazio dell'heap perché faccio una lista di tutti i numeri fino a lim, e poi li filtra via uno alla volta mentre sposto il primo in un nuovo elenco. (Lo so che sto facendo in realtà nuovi elenchi ogni ripresentarsi, ma non pensavo che avrebbero preso più memoria?) Comunque Sto facendo funzionare questo con

(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 

E continuo a corto di spazio di heap, quando chiamo

(apply + (getAllPrimes 2000000)) 

, ma io non esaurire lo spazio sul

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

Quindi penso che non devo capire come liste sono spazzatura raccolti nelle chiamate a ripresentarsi e sono in realtà usando O (n * n) heap o qualcosa.

Answer 1

Credo che il problema sia che a ogni ripetizione si sta creando una nuova sequenza pigra riferita all'ultima, quindi dopo alcune iterazioni si sta tenendo un seq che contiene la testa di un seq che tiene la testa di un seq che contiene la testa di un seq. ... Tutti i seq intermedi stanno riempiendo il tuo mucchio.

Anche se scrivere un setaccio principale è un esercizio utile, se si vuole ottenere la risposta, Clojure include la sequenza dei numeri primi nella sua libreria standard: clojure.contrib.lazy-seqs/primi. La soluzione standard a questo particolare problema di Eulero è una soluzione unica.

Come punto di stile, un defn interno non è una buona idea. L'effetto pratico è lo stesso come se il defn fosse al livello più alto, ma se non sbaglio, il var viene riassegnato ogni volta che viene chiamato getAllPrimes e la ridefinizione dei vars in runtime è fortemente scoraggiata. Poiché il codice sta semplicemente definendo una var, getPrimes è ancora visibile come getAllPrimes. In questo caso, getPrimes potrebbe facilmente essere riscritto come un loop/ricorrenza senza funzioni interne, anonime o con nome. Che non aiuta la vostra catena-di-lazy-seguenti del regolamento provvisorio problema, ma rende il codice un po 'più normale di aspetto:

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

vorrei anche evitare l'uso di camelCase. Il nome standard di Clojure per questa funzione sarebbe get-all-primi.

Tornando al problema pratico, tuttavia, il minimo lavoro che si potrebbe fare per far funzionare il codice sarebbe forzare ogni seq su ogni iterazione, cioè, avvolgere la chiamata filtro in un doall. Ho provato questo, e mentre corre ancora lentamente, almeno ha gestito fino al completamento senza esaurire mucchio:

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