我有一个关于Clojure的问题：
我试图通过浏览 Project Euler学习语言,我不明白幕后发生了什么：下面的代码旨在使用返回所有素数列表到lim.我认为它应该是堆空间中的O(n),因为我列出了所有数字到lim的列表,然后逐个过滤它们,同时将第一个数字移动到新的列表. (我知道我实际上是在制作新的列表,但是我认为它们不会占用更多内存吗？)无论如何我运行这个
我试图通过浏览 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)))
解决方法
我相信问题在于,每次重复时,你都会创建一个新的延迟序列,指向最后一个,所以在几次迭代之后,你持有一个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)))
