关于Clojure中的堆和垃圾的初学者问题

Question

我有一个关于Clojure的问题:我正在尝试通过项目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)))

所以我认为我不能理解如何在对recur的调用中收集垃圾,并且实际上是在使用O(n*n)堆或其他东西.

Answer 1

我相信问题在于,每次重复时,你都会创建一个新的延迟序列,引用最后一个,所以在几次迭代之后,你持有一个seq,它包含一个seq的头部,它包含一个seq的头部.掌握一个seq的头.......所有的中间序列都填满了你的堆.

虽然写一个主要筛子是值得的,但如果你想得到答案,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)))

我也会避免使用camelCase.此函数的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)))