39

我正在尝试编写一个简单的筛子函数来计算 clojure 中的素数。我见过这个关于编写有效筛子函数的问题，但我还没有到那个地步。现在我只是想写一个非常简单（而且很慢）的筛子。这是我想出的：

(defn sieve [potentials primes]
  (if-let [p (first potentials)]
    (recur (filter #(not= (mod % p) 0) potentials) (conj primes p))
    primes))

对于小范围，它可以正常工作，但会导致大范围的堆栈溢出：

user=> (sieve (range 2 30) [])
[2 3 5 7 11 13 17 19 23 29]
user=> (sieve (range 2 15000) [])
java.lang.StackOverflowError (NO_SOURCE_FILE:0)

我认为通过使用recur这将是一个不消耗堆栈的循环结构？我错过了什么？

4

2 回答 2

57

你被filter他的懒惰打击了。更改(filter ...)为(doall (filter ...))您的recur表格，问题应该消失。

更深入的解释：

调用filter返回一个惰性序列，它根据需要具体化过滤序列的实际元素。正如所写的那样，您的代码堆叠filter在...filter上，在每次迭代filter中增加一个级别；filter在某些时候，这会爆炸。解决方案是在每次迭代时强制整个结果，以便下一次将对完全实现的 seq 进行过滤并返回完全实现的 seq，而不是添加额外的惰性 seq 处理层；就是doall这样。

于 2010-06-01T01:34:59.293 回答
-1

从算法上讲，问题在于您在没有更多目的时继续过滤。尽早停止可以实现递归深度的二次减小（sqrt(n)vs. n）：

(defn sieve [potentials primes]    
  (if-let [p (first potentials)]
      (if (> (* p p) (last potentials))
        (concat primes potentials)
        (recur (filter (fn [n] (not= (mod n p) 0)) potentials)
               (conj primes p)))
    primes))

在 ideone 上运行 16,000 次（仅执行 30 次迭代而不是 1862 次）和 160,000次运行良好。即使没有doall.

于 2017-01-12T19:06:49.300 回答