Clojure - Eratosthenes 的尾递归筛法 [英] Clojure - tail recursive sieve of Eratosthenes
本文介绍了Clojure - Eratosthenes 的尾递归筛法的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我在 Clojure 中实现了 Eratosthenes 筛法:
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))))))
对于较大的 n
(如 20000),它以堆栈溢出结束.为什么尾调用消除在这里不起作用?如何解决?
For larger n
(like 20000) it ends with stack overflow. Why doesn't tail call elimination work here? How to fix it?
推荐答案
问题:filter
执行惰性求值,因此每个新级别的过滤都在调用堆栈上徘徊.
Problem: filter
does lazy evaluation, so each new level of filtering hangs around on the call stack.
修复:将 (filter ...)
更改为 (doall (filter ...))
.
Fix: Change (filter ...)
to (doall (filter ...))
.
在此处查看说明.
这篇关于Clojure - Eratosthenes 的尾递归筛法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文