Clojure - 埃拉托斯特尼的尾递归筛
我在 Clojure 中实现了埃拉托斯特尼筛法：
(defn sieve [n]
(loop [last-tried 2 sift (range 2 (inc n))]
(if
(or (nil? last-tried) (> last-tried n))
sift
(let [filtered (filter #(or (= % last-tried) (< 0 (rem % last-tried))) sift)]
(let [next-to-try (first (filter #(> % last-tried) filtered))]
(recur next-to-try filtered))))))
对于较大的 n （如 20000），它会以堆栈溢出结束。为什么尾调用消除在这里不起作用？如何修复它？
I have this implementation of the sieve of Eratosthenes in Clojure:
(defn sieve [n]
(loop [last-tried 2 sift (range 2 (inc n))]
(if
(or (nil? last-tried) (> last-tried n))
sift
(let [filtered (filter #(or (= % last-tried) (< 0 (rem % last-tried))) sift)]
(let [next-to-try (first (filter #(> % last-tried) filtered))]
(recur next-to-try filtered))))))
For larger n (like 20000) it ends with stack overflow. Why doesn't tail call elimination work here? How to fix it?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
问题：
filter执行延迟计算，因此每个新级别的过滤都会挂在调用堆栈上。修复：将
(filter ...)更改为(doall (filter ...))。请参阅此处的说明。
Problem:
filterdoes lazy evaluation, so each new level of filtering hangs around on the call stack.Fix: Change
(filter ...)to(doall (filter ...)).See the explanation here.
如果你看一下回溯，
它看起来像这样：
是太多的过滤器导致了溢出，而不是循环。
不幸的是，我没有看到明显的解决方案。
If you look at the backtrace
it looks like this:
It's too many filters that's causing the overflow, not the loop.
Unfortunately, I don't see an obvious solution for this.
我赞同 Michal Marczyk 关于查看 cgrande 美丽的增量 SoE 的评论。我做了一些非常原始的基准测试，并将它们放在 http://clojure.roboloco.net/?p =100，适合那些对惰性素数生成器性能感兴趣的人。
I second Michal Marczyk's comment about checking out cgrande's beautiful incremental SoE. I did some really primitive benchmarks and put them up at http://clojure.roboloco.net/?p=100, for those curious about lazy prime generator performance.