Débutant question à propos de tas et des ordures à Clojure

Question

J'ai une question à propos de Clojure: J'essaie d'apprendre la langue en passant par Project Euler et je ne comprends pas ce qui se passe sous le capot: Le code suivant est conçu pour utiliser renvoie une liste de tous les nombres premiers jusqu'à lim. Je pense qu'il devrait être O (n) dans l'espace de tas parce que je fais une liste de tous les nombres jusqu'à lim, puis les filtre un par un tout en déplaçant le premier à une nouvelle liste. (Je sais que je suis en fait faire de nouveaux listes chaque RECUR mais je ne pensais pas qu'ils prendraient plus de mémoire?) De toute façon je courais cela avec

(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 

Et je continue à manquer d'espace de tas, quand je l'appelle

(apply + (getAllPrimes 2000000)) 

, mais je ne lance pas d'espace sur

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

Je pense donc que je ne dois pas comprendre comment les listes sont recueillies dans les ordures appels à se reproduire et je suis réellement en utilisant O (n * n) tas ou quelque chose.

Answer 1

Je crois que le problème est qu'à chaque récurrence, vous créez une nouvelle séquence paresseuse se référant à la dernière, donc après quelques itérations, vous tenez un seq qui contient la tête d'un seq qui tient la tête d'un seq qui tient la tête d'un seq. ... Tous les seqs intermédiaires remplissent votre tas.

Bien que l'écriture d'un premier crible soit un exercice intéressant, si vous voulez obtenir la réponse, Clojure inclut la séquence des nombres premiers dans sa bibliothèque standard: clojure.contrib.lazy-seqs/primes. La solution standard à ce problème particulier d'Euler est un one-liner.

En tant que point de style, une définition interne n'est pas une bonne idée. L'effet pratique est le même que si les defn étaient au plus haut niveau, mais si je ne me trompe pas, la variable var est réaffectée chaque fois que getAllPrimes est appelée, et la redéfinition des variables à l'exécution est fortement déconseillée. Puisque le code ne fait que définir une variable, getPrimes est toujours aussi visible que getAllPrimes. Dans ce cas, getPrimes pourrait facilement être réécrit comme une boucle/récurrente sans fonction interne, anonyme ou nommée. Cela ne nous aide pas votre chaîne de-seqs paresseux problème, mais il ne fait le code un peu plus standard à la recherche:

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

Je voudrais aussi éviter l'utilisation de camelCase. Le nom standard de Clojure pour cette fonction serait get-all-primes. Cependant, pour en revenir au problème pratique, le moindre travail que vous pourriez faire pour que votre code fonctionne serait de forcer chaque seq à chaque itération, c'est-à-dire d'envelopper votre appel de filtre dans un doall. J'ai essayé, et pendant qu'il tourne encore lentement, au moins ne fonctionne à l'achèvement sans manquer de tas:

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