performance - Prime sieve 导致(我要去)堆栈溢出

Question

对于欧拉项目，我一直在寻找一种方法来实现埃拉托色尼筛法，因为我希望它比我最初的实现更快(并且需要它如此)。我想出了这个功能:

sieve :: Int -> [Int] -> [Int]
sieve p (x:xs) | rem x p == 0 = sieve p xs
               | otherwise = x : (sieve x $ sieve p xs)
sieve _ [] = []

这行得通，但风扇速度非常快，导致堆栈溢出。我前往这里寻求建议并立即点击了spoiler对我来说，这看起来完全一样，但性能上的差异是古怪的。我仍然想继续使用我自己的实现，并且想知道是否可以轻松更改我的函数以使用更少的内存。

Answer 1

您的代码内部呈指数级增长:

sieve p (x:xs) | rem x p == 0 = sieve p xs
               | otherwise = x : (sieve x $ sieve p xs)
--                                          ^^^^^^^       here!
--                                ^^^^^^^                 and here!

您打算让内部 sieve 调用继续通过 p 进行过滤，但是由于您使用相同的 sieve 函数，它也会在遇到新质数时为新质数启动新过滤器 - 但这是完全多余的，因为“上层”调用也会为相同质数启动新过滤器!

sieve 2 [3..]
 = 3 : sieve 3 (sieve 2 [4..])
 = 3 : sieve 3 (5 : sieve 5 (sieve 2 [6..]))
 = 3 : 5 : sieve 5 (sieve 3 (sieve 5 (sieve 2 [6..])))
....         -- ^^^               ^^^                      -- !!!

在 7 通过这里的四个 sieve 到达顶部后，每个都会分成两部分，创建四个新的 sieve 7，所以链中将有​​八个 sieve!!更糟糕的是，当 9 - 合成! - 通过筛子，它将 split 2、7 和 5，并且只会被 拒绝3。所以它实际上比指数级的素数 n 还差，并且接近指数级的最后一个素数产生的值(n em>~ n log(n)).

改成

sieve p (x:xs) | rem x p == 0 = sieve p xs
               | otherwise = x : (sieve x $ filter ((>0).(`rem` p)) xs)

然后您将获得与您引用的代码等效的代码。

如果您喜欢手动编写所有代码，您可以引入一个新参数，一个控制是否启动新过滤器的 bool 标志:

primes = 2 : sieve True 2 [3..]
sieve b p (x:xs) | rem x p == 0 = sieve b p xs
                 | b = x : (sieve b x $ sieve False p xs)
                 | otherwise = x : sieve b p xs