performance - Prime sieve 导致（我要去）堆栈溢出

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次通过这里的 4 个 s 到顶部后sieve，每个会分裂成 2 个，产生 4 个新sieve 7的 s，所以链上有8 个s！ sieve更糟糕的是，当9 - 复合！- 穿过筛子，它将2、7 s 和5分开，并且只会被3拒绝。所以它实际上比素数的指数更差n，并且接近于产生的最后一个素数的值（即~ n log(n)）的指数。

将其更改为

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

你得到的代码与你引用的代码相同。

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

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