clojure - 使用 Remove 生成​​素数时出现段错误和堆错误

Question

我正在尝试编写一个筛子来为 Project Euler 问题生成素数。

代码如下所示:

(defn sieve [n]
  (reduce (fn [memo f]
              (remove #(and (= 0 (rem % f))
                            (not= % f))
                      memo))
          (range 2 (+ 1 n))
          (range 2 (+ 1 n))))

直到 500000 它运行得非常快，不到 1 秒，从 600000 开始它开始段故障
并因内存错误而崩溃。

我想它与删除和懒惰有关，我搜索了一下，尝试使用 (doall (remove ...)) 而不是 (remove) 但它变得非常慢......

我对此有点不知所措，在此先感谢您的帮助...

Answer 1

段错误？这听起来很可怕!我假设您的意思是堆栈溢出错误。

当我运行该函数时，我开始在大约 1000 处出现堆栈溢出错误。那么为什么堆栈溢出呢？这与懒惰有关。 解决方法是将要删除的调用包装在一个 doall 中。

Reduce 将遍历作为第三个参数给出的序列中的每个元素，并在此过程中保持一个状态。这个状态被初始化为从 2 到 n+1 的整数范围。使用remove在每次迭代时更新状态。然而，由于 remove 是惰性的，它实际上不会做任何事情。 Remove 将返回一个对象，该对象可以根据给定的序列按需生成序列。我将尝试通过一个例子来解释这一点:

(reduce (fn [xs x] (remove #{x} xs)) coll (range 4))

上面的表达式将返回 coll 元素的序列，但过滤掉了数字 0 到 3。为了解释运行时发生的情况，我将发明一种新的表示法:我将写出运行时值 (remove #{x} xs)如 «I.O.U. a seq like xs but with x removed» .然后，reduce 表达式的值是:

«I.O.U. a seq like
  «I.O.U. a seq like
    «I.O.U. a seq like
      «I.O.U. a seq like 'coll' but with 0 removed»
    but with 1 removed»
  but with 2 removed»
but with 3 removed»

每次调用 remove 都会添加一个包装“I.O.U.”。当您最终尝试访问结果序列的第一个值(最外面的“I.O.U.”值)时，这会导致问题。当一个惰性序列对象被遍历时，首先检查它的值是否已经被计算。如果该值已经完成，则简单地返回该值。如果不是，则计算、存储并返回它。

当一个延迟序列(“I.O.U.”值)需要强制另一个延迟序列能够执行其工作时，就会出现问题，因为每个延迟序列实现都需要一个堆栈帧。 (需要一个堆栈帧来记住当第二个延迟序列完成时返回到哪里。)如果你有 1000 个嵌套的“I.O.U.”值，您需要 1000 个堆栈帧来实现它们(假设它们最初都未实现)。

解决方案是使用 Clojure 标准库中的 doall 函数。它需要一个 seq 并使其完全实现。如果您将调用 remove 包装在 doall 中，reduce 状态将始终包含每次迭代之间完全实现的 seq，并且不会出现“I.O.U.”级联。值(value)观会建立起来。您不是保存所有计算以备日后使用，而是逐步进行。