haskell - 为什么这个主要测试这么慢？

Question

这段代码取自《Haskell Road to Logic, Math and Programming》一书。它实现了埃拉托色尼筛算法并解决了 Project Euler 问题 10。

sieve :: [Integer] -> [Integer]
sieve (0 : xs) = sieve xs
sieve (n : xs) = n : sieve (mark xs 1 n)
  where
    mark :: [Integer] -> Integer -> Integer -> [Integer]
    mark (y:ys) k m | k == m = 0 : (mark ys 1 m)
                    | otherwise = y : (mark ys (k+1) m)

primes :: [Integer]
primes = sieve [2..]

-- Project Euler #10
main = print $ sum $ takeWhile (< 2000000) primes

实际上，它的运行速度甚至比天真的素数测试还要慢。
有人可以解释这种行为吗？

我怀疑这与在标记函数中迭代列表中的每个元素有关。

谢谢。

Answer 1

您正在使用此算法构建二次未评估的 thunk。该算法严重依赖惰性，这也是它无法扩展的原因。

让我们来看看它是如何工作的，希望这能让问题变得明显。简单来说，假设我们想要 print primes 的元素ad infinitum，即我们想要一个接一个地评估列表中的每个单元格。 primes定义为:

primes :: [Integer]
primes = sieve [2..]

由于 2 不为 0， sieve 的第二个定义适用，并且 2 被添加到素数列表中，并且列表的其余部分是未评估的 thunk(我使用 tail 而不是 n : xs 中的模式匹配 sieve 为 xs ，所以 tail ' 实际上没有被调用，并且不会在下面的代码中增加任何开销； mark 实际上是唯一的 thunked 函数):

primes = 2 : sieve (mark (tail [2..]) 1 2)

现在我们想要第二个 primes元素。因此，我们遍历代码(读者练习)并最终得到:

primes = 2 : 3 : sieve (mark (tail (mark (tail [2..]) 1 2)) 1 3)

再次相同的过程，我们要评估下一个素数......

primes = 2 : 3 : 5 : sieve (mark (tail (tail (mark (tail (mark (tail [2..]) 1 2)) 1 3))) 1 5)

这开始看起来像 LISP，但我离题了......开始看到问题了吗？对于 primes 中的每个元素列表，越来越多的 mark 堆栈必须对应用程序进行评估。换句话说，对于列表中的每个元素，必须通过评估每个 mark 来检查该元素是否由前面的任何素数标记。堆栈中的应用程序。所以，对于 n~=2000000 ，Haskell 运行时必须调用函数，导致调用堆栈的深度约为 ... 我不知道，137900( let n = 2e6 in n / log n 给出了下限)？类似的东西。这可能是导致减速的原因；也许 vacuum 可以告诉你更多(我现在没有一台同时具有 Haskell 和 GUI 的计算机)。

Eratosthenes 的筛子在像 C 这样的语言中起作用的原因是:

您没有使用无限列表。

由于 (1)，您可以在继续下一个 n 之前标记整个数组，根本没有调用堆栈开销。