Clojure - 迭代惰性集合时出现 StackOverflowError

Question

我目前正在 Clojure 中实现欧拉项目问题之一的解决方案，即埃拉托斯特尼筛法 ( https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes )。这是我的代码:

(defn cross-first-element [coll]
  (filter #(not (zero? (rem % (first coll)))) coll))

(println
  (last
  (map first
    (take-while
      (fn [[primes sieve]] (not (empty? sieve)))
      (iterate
        (fn [[primes sieve]] [(conj primes (first sieve)) (cross-first-element sieve)])
        [[] (range 2 2000001)])))))

基本思想是有两个集合 - 已经从筛子中检索到的素数，以及剩余的筛子本身。我们从空的primes开始，直到筛子为空，我们选择它的第一个元素并将其附加到primes，然后我们从筛子中划掉它的倍数。当它耗尽时，我们知道我们拥有素数中 200 万以下的所有素数。

不幸的是，尽管它适用于较小的筛子上限(例如 1000)，但它会导致 java.lang.StackOverflowError 并具有长堆栈跟踪，并且重复序列为:

...
clojure.lang.RT.seq (RT.java:531)
clojure.core$seq__5387.invokeStatic (core.clj:137)
clojure.core$filter$fn__5878.invoke (core.clj:2809)
clojure.lang.LazySeq.sval (LazySeq.java:42)
clojure.lang.LazySeq.seq (LazySeq.java:51)
...

我的解决方案中的概念错误在哪里？如何解决？

Answer 1

原因如下:由于 cross-first-element 中的 filter 函数是惰性的，因此它实际上不会在每个 上过滤您的集合code>iterate 步骤，而是“堆栈”过滤器函数调用。这会导致这样的情况:当您实际需要结果元素时，将执行整个测试函数负载，大致如下:

(#(not (zero? (rem % (first coll1))))
  (#(not (zero? (rem % (first coll2))))
    (#(not (zero? (rem % (first coll3))))
       ;; and 2000000 more calls

导致堆栈溢出。

您的情况最简单的解决方案是让过滤变得急切。您可以简单地使用 filterv 而不是 filter 来完成此操作，或者将其包装到 (doall (filter ...

但是你的解决方案仍然非常慢。我宁愿使用循环和 native 数组。