使用 haskell 的 Project Euler prob 10

Question

好的，所以我做了一个小修改，似乎对 haskell 产生了很大的影响。事情是这样的：

我为欧拉项目的 Prob 10 实施了埃拉托色尼筛法。这是怎么回事：

primesBelowN :: Integer -> [Integer]
primesBelowN n = 2:3:filter f [6*k+i | k <- [1..(n-1)`div`6], i <- [-1, 1]]
                 where f x = foldr g True [2..truncate(sqrt(fromInteger x))]
                             where g t ac = (x `rem` t /= 0) && ac

main = print $ sum $ primesBelowN 2000000

用 ghc 编译，运行时间为 8.95 秒：

$ ghc -O3 010SummationOfPrimes.hs
$ time 010SummationOfPrimes
142913828922
8.739u 0.122s 0:08.95 98.8% 0+0k 2384+0io 1pf+0w

我认为我可以通过利用 haskell 在 g 函数中的惰性求值来优化代码。可以通过简单地将 ac 作为 && 的第一个参数来完成（或者我认为），这样它就不会计算 ac == False:

的不等式

primesBelowN :: Integer -> [Integer]
primesBelowN n = 2:3:filter f [6*k+i | k <- [1..(n-1)`div`6], i <- [-1, 1]]
                 where f x = foldr g True [2..truncate(sqrt(fromInteger x))]
                             where g t ac = ac && (x `rem` t /= 0)

main = print $ sum $ primesBelowN 2000000

令人惊讶的是，它使程序慢了 4 倍！。现在的运行时间明显变大了，为 30.94 秒：

$ ghc -O3 010SummationOfPrimes.hs
$ time 010SummationOfPrimes
142913828922
30.765u 0.157s 0:30.94 99.9%    0+0k 2384+0io 1pf+0w

我不知道出了什么问题...任何 hints/suggestions/answers？提前致谢！

编辑

所以，我在玩这个的时候不小心摔倒了。如果我像这样调整我的函数，看起来很容易陷入无限循环：

primesBelowN :: Integer -> [Integer]
primesBelowN n = 2:3:filter f [6*k+i | k <- [1..(n-1)`div`6], i <- [-1, 1]]
                 where f x = foldr g True [m | m <- [2..], 
                                               m <= truncate(sqrt(fromInteger x))]
                             where g t ac = (x `rem` t /= 0) && ac

main = print $ sum $ primesBelowN 2000000

在这种情况下，进程内存一直爆炸到巨大的数字（80Gig，在我杀死它之前），没有任何输出：

$ ghc -O3 010SummationOfPrimes.hs
$ time 010SummationOfPrimes
^C20.401u 7.994s 0:28.42 99.8%  0+0k 2384+0io 1pf+0w

知道现在出了什么问题吗？

Answer 1

对于问题的第一部分，请注意 foldr 的运作方式：

foldr g x0 [x1, x2, x3, .., xn] = g x1 (g x2 (g x3 (..(..(g xn x0)))..)

在我们的案例中，

foldr g True [2..truncate(sqrt(fromInteger x))]
      where g t ac = (x `rem` t /= 0) && ac

相当于：

foldr g True (map h [2..truncate(sqrt(fromInteger x))])
      where g t ac = t && ac
            h t = x `rem` t /= 0

相当于：

foldr (&&) True (map h [2..truncate(sqrt(fromInteger x))])
      where h t = x `rem` t /= 0

而这又等同于：

(h x1) && ((h x2) && ((h x3) &&(....((h xn) && True)))..)

请记住，我们正在处理一种惰性语言，其中评估由模式匹配引导。 && 仅在其第一个参数中是严格的，这意味着除非必要，否则不必生成第二个参数表达式，即使这样它也只需要继续直到 (h x2) 处于最外层。因此，更/适当的/表示是这样的（部分伪代码）：

(h x1) && {instructions to generate (h x2) && ((h x3) && (....((h xn) && True)))..)}

因此，计算完整的 && 表达式所需的内存大部分是恒定的。我们只需要保留 (h x1) 和生成下一个值的指令。如果 (h x1) 是 False 我们停止，否则我们丢弃它并生成另一对值和指令。这显然不是 haskell 的实际实现方式，但足以作为模型。

现在，如果您切换参数顺序，&& 将必须首先计算第二个参数的表达式，其中 && 将依次必须完全计算下一个子表达式，依此类推，要求所有中间值都保留在堆栈中，直到整个表达式完全扩展并根据需要进行评估。另请注意，余数检查将以相反的顺序进行，这使得该过程更加低效，因为与较小的素数相比，合数不太可能是较大素数的倍数。因此，总运行时间和内存需求更差。

关于问题的第二（已编辑）部分，问题是您不再使用有限列表。对列表理解的限制用作过滤而不是限制。为了 foldr 使用 && 完成，您需要提供一个空列表（这对于无限列表的定义是不可能的）或针对谓词 [ 的列表的单个元素进行模式匹配=48=]s False。不幸的是，在某些情况下（x 是质数）谓词不会 return False 并且 foldr 将继续尝试与它会匹配的另一个元素进行模式匹配。所有这一切都是徒劳的，因为在一个点之后不会因为守卫而产生更多的元素。它失败的原因与失败的原因几乎相同：

head $ filter (const False) [1..]

使用 haskell 的 Project Euler prob 10

Project Euler prob 10 using haskell

optimization

primes

haskell

lazy-evaluation

ghc