关于Clojure堆和垃圾的初级问题

Question

我有一个关于Clojure的问题： 我想通过Project Euler去学习语言，我不明白底下发生了什么：下面的代码是为了使用返回所有素数列表，最高可达lim。我认为它应该是堆空间中的O（n），因为我列出了所有数字列表，最多为lim，然后逐个将它们过滤掉，同时将第一个移动到新列表中。 （我知道，我其实做新列出了每个易复发，但我没想到他们会采取更多的内存？）反正我与

(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 

运行这和我保持运行的堆空间不足，当我打电话

(apply + (getAllPrimes 2000000)) 

，但我不上

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

用完的空间，所以我认为我不能明白名单是如何收集垃圾的通话复发和我实际使用O（N * n）堆什么的。

Answer 1

我相信问题在于，每次重复发生时，您都会创建一个指向最后一个的新延迟序列，因此经过几次迭代后，您将持有一个seq来保存头部seq的头部持有seq头的seq。 ...所有的中间seqs填满你的堆。

虽然编写一个主筛是一个有价值的练习，但如果你想要得到答案，Clojure确实在其标准库中包含素数序列：clojure.contrib.lazy-seqs/primes。这个特殊的欧拉问题的标准解决方案是一个线性的。

作为一个风格点，内心不是一个好主意。实际效果与defn处于顶层时相同，但如果我没有弄错，每次调用getAllPrimes时都会重新分配var，并且在运行时重新定义变量非常令人沮丧。由于代码只是定义了一个var，所以getPrimes仍然和getAllPrimes一样可见。在这种情况下，getPrimes很容易被重写为一个没有内部函数的匿名或命名的循环/循环。这不利于您的链方面的懒惰seqs问题，但它确实使代码多一点标准的前瞻性：

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

我还要避免使用驼峰的。这个函数的Clojure标准名称是get-all-primes。回到实际问题，尽管如此，为使代码正常工作所做的最少的工作是在每次迭代中强制每个seq，即将过滤器调用包装在doall中。我想这一点，虽然它仍然运行速度慢，它至少会运行到完成，而且没有用完堆：

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