代码之家 › 专栏 › 技术社区 › Konrad Garus

埃拉托斯滕的Clojure-尾递归筛

sieve-of-eratosthenes primes functional-programming clojure algorithm

Konrad Garus · 技术社区 · 14 年前

我在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)它以堆栈溢出结束。为什么尾叫消除在这里不起作用?如何修复?

3 回复 | 直到 8 年前

Community Michael Schmitz 7 年前

问题: filter 执行延迟计算,因此每个新的过滤级别都挂在调用堆栈上。

修正:改变 (filter ...) 到 (doall (filter ...)) .

请看解释 here .

cobbal 14 年前

如果你看看回溯

(try
 (sieve 200000)
 (catch java.lang.StackOverflowError e
  (.printStackTrace e)))

看起来是这样的:

...
at clojure.lang.LazySeq.sval(LazySeq.java:42)
at clojure.lang.LazySeq.seq(LazySeq.java:56)
at clojure.lang.RT.seq(RT.java:440)
at clojure.core$seq__4176.invoke(core.clj:103)
at clojure.core$filter__5033$fn__5035.invoke(core.clj:1751)
at clojure.lang.LazySeq.sval(LazySeq.java:42)
at clojure.lang.LazySeq.seq(LazySeq.java:56)
...

太多的过滤器导致溢出,而不是循环。

不幸的是,我没有看到一个明显的解决方案。

ivar 14 年前

我附和了迈克尔·马尔茨克关于检查cgrande漂亮的增量SOE的评论。我做了一些非常原始的基准测试 http://clojure.roboloco.net/?p=100 对于那些好奇于惰性的主发电机性能的人。

推荐文章

Jihyun · 整合功能要慢得多

7 年前

Fusionist · 素数逻辑,循环中的n/2条件

7 年前

Milad · JavaScript中的素数

7 年前

distro · 具有流控制的嵌套列表理解

7 年前

Frenchi33 · 双素数对公式

7 年前

Renee · 打印所有小于50的素数[重复]

7 年前

marcosh · Idris-定义素数类型

7 年前

Marcus · 在Python中查找素数

7 年前

AmR · Python使用count()初始化迭代器

7 年前

Hanzy · 对于循环,语法错误:无法分配给函数调用[closed]

7 年前