總理篩結果（我要）堆棧溢出

Question

對於項目歐拉我正在尋找一種方法來實施Eratosthenes篩，因爲我預計它比我的原始實施（並需要它是如此）更快。我想出了這個功能：

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..]))) 
....   -- ^^^    ^^^      -- !!! 

後通過四個sieve這兒穿過頂端，每一個將在兩創建四個新sieve 7而分裂，所以會有sieve S IN的鏈!!更糟的是，當 - 複合！ - 經過篩子，將分割，所述 S和，並且將僅由被拒絕。所以它實際上糟糕比指數中的素數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