9

我在 Clojure 中有这个 Eratosthenes 筛子的实现：

(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）它以堆栈溢出结束。为什么尾部呼叫消除在这里不起作用？如何解决？

4

3 回答 3

12

问题：filter进行惰性评估，因此每个新级别的过滤都挂在调用堆栈上。

修复：更改(filter ...)为(doall (filter ...)).

请参阅此处的说明。

于 2010-06-05T14:05:56.707 回答
2

如果你看回溯

(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)
...

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

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

于 2010-06-05T13:55:02.243 回答
0

我赞同 Michal Marczyk 关于查看 cgrande 漂亮的增量 SoE 的评论。我做了一些非常原始的基准测试并将它们放在http://clojure.roboloco.net/?p=100上，供那些对惰性素数生成器性能感兴趣的人使用。

于 2010-06-09T03:16:34.863 回答