Clojure

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，然后我们从筛子中划掉它的倍数。当它耗尽时，我们知道我们拥有所有从两百万以下的素数。

不幸的是，尽管它适用于筛子的小上限（比如 1000），但它会导致 java.lang.WhosebugError 具有长堆栈跟踪，重复序列为：

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

您已经（重新）发现嵌套惰性序列有时会出现问题。 Here is one example 可能出错的地方（不直观）。

如果您不介意使用库，那么使用围绕命令式循环的单个惰性包装器，问题就会简单得多。这就是 lazy-gen 和 yield 给你的（Python 中的 "generators"）：

(ns tst.demo.core
  (:use demo.core tupelo.test)
  (:require [tupelo.core :as t]))

(defn unprime? [primes-so-far candidate]
  (t/has-some? #(zero? (rem candidate %)) primes-so-far))

(defn primes-generator []
  (let [primes-so-far (atom [2])]
    (t/lazy-gen
      (t/yield 2)
      (doseq [candidate (drop 3 (range))] ; 3..inf
        (when-not (unprime? @primes-so-far candidate)
          (t/yield candidate)
          (swap! primes-so-far conj candidate))))))

(def primes (primes-generator))

(dotest
  (is= (take 33 primes)
    [2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 ])

  ; first prime over 10,000
  (is= 10007 (first (drop-while #(< % 10000) primes)))

  ; the 10,000'th prime (https://primes.utm.edu/lists/small/10000.txt)
  (is= 104729 (nth primes 9999)) ; about 12 sec to compute
)

我们也可以使用 loop/recur 来控制循环，但是使用 atom 来保持状态更容易阅读。

除非你真的，真的需要一个惰性和无限的解决方案，命令式的解决方案要简单得多：

(defn primes-upto [limit]
  (let [primes-so-far (atom [2])]
    (doseq [candidate (t/thru 3 limit)]
      (when-not (unprime? @primes-so-far candidate)
        (swap! primes-so-far conj candidate)))
    @primes-so-far))

(dotest
  (is= (primes-upto 100)
    [2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97]) )

Answer 2

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

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

导致堆栈溢出。

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

但您的解决方案仍然很慢。我宁愿为此使用循环和本机数组。

Clojure - 迭代惰性集合时发生 StackOverflowError

Clojure - StackOverflowError while iterating over lazy collection

stack-overflow

lazy-evaluation