12

这是我在 Clojure 中对 Erathosthene 筛的实现（基于关于流的 SICP 课程）：

(defn nats-from [n]
  (iterate inc n))

(defn divide? [p q]
  (zero? (rem q p)))

(defn sieve [stream]
  (lazy-seq (cons (first stream)
            (sieve (remove #(divide? (first stream) %) 
               (rest stream))))))

(def primes (sieve (nats-from 2)))

现在，当我取前 100 个素数时，一切正常：

(take 100 primes)

但是，如果我尝试取前 1000 个素数，程序会因为堆栈溢出而中断。我想知道是否有可能以某种方式将函数筛更改为尾递归，并且仍然保留算法的“流”？

有什么帮助？？？

4

1 回答 1

10

首先，这不是 Eratosthenes 的筛子……有关详细信息，请参阅我的评论。

其次，为近距离投票表示歉意，因为您的问题与我所指出的问题并不完全相同……我的错。

正在发生的事情的解释

不同之处当然在于您正在尝试构建一个增量筛，其中remove调用工作的范围是无限的，因此不可能只doall围绕它进行包装。解决方案是从我最近似乎经常链接到的论文中实现“真正的”增量 SoE 之一——Melissa E. O'Neill 的The Genuine Sieve of Eratosthenes。

Christophe Grand 编写了一个特别漂亮的 Clojure 筛子实现，供所有可能感兴趣的人欣赏。强烈推荐阅读。

至于问题的根源，我最初认为你的问题是重复的，其中包含对你有用的解释：请参阅此处和此处。再次，对于草率的投票结束感到抱歉。

为什么尾递归无济于事

由于问题特别提到了将筛选函数 tail-recursive 作为一种可能的解决方案，我想我会在这里解决这个问题：转换惰性序列的函数通常不应该是 tail recursive。

这是需要牢记的非常重要的一点，它会绊倒许多没有经验的 Clojure（或 Haskell）程序员。原因是尾递归函数必须在它“准备好”时才返回它的值——在计算的最后。（迭代过程可以在任何特定迭代结束时返回一个值或继续下一次迭代。）相反，生成惰性序列的函数应该立即返回一个惰性序列对象，该对象封装了代码位，这些代码位可以要求在需要时生成序列的头部或尾部。

因此，堆叠惰性转换问题的答案不是使任何尾递归，而是合并转换。在这种特殊情况下，可以通过使用自定义方案来融合基于优先级队列或映射的过滤操作来获得最佳性能（有关详细信息，请参阅上述文章）。

于 2010-06-07T19:18:01.863 回答