++，last＆init快於：，head＆tail？

Question

鑑於編寫查找所有素數的函數的這兩種方式達到特定號碼：

primes1 = iterate 
    (\ps -> ps ++ [([x | 
     x <- [last ps + 1..], 
     all (\p -> x `mod` p /= 0) ps] !! 0)]) 
    [2] 

primesTo1 :: Integer -> [Integer] 
primesTo1 n = init $ head $ dropWhile (\p -> last p <= n) primes1 

primes2 = iterate 
    (\ps -> ([x | 
      x <- [head ps + 1..], 
      all (\p -> x `mod` p /= 0) ps] !! 0) 
     : ps) 
    [2] 

primesTo2 :: Integer -> [Integer] 
primesTo2 n = tail $ head $ dropWhile (\p -> head p <= n) primes2 

爲什麼primesTo1比primesTo2快了很多，即使使用不同的功能; primesTo1使用++，last & init代替:，head & tail在primesTo2使用。

的ghci輸出與:set +s：

*Main> primesTo1 10000 
... 
(0.51 secs, 124779776 bytes) 
*Main> primesTo2 10000 
... 
(3.30 secs, 570648032 bytes) 

與ghc -O2編譯：

$ time ./primes1 
... 
./primes1 0.06s user 0.00s system 68% cpu 0.089 total 
$ time ./primes2 
... 
./primes2 0.28s user 0.00s system 98% cpu 0.283 total 

---

注：我不是找Haskell的最佳素數生成器，我我只是被兩個函數的速度差所迷惑。

Answer 1

正如「n.m.」所指出的，原因是primes2首先嚐試除以最大的找到的素數，而primes1從最低開始。

所以首先扭轉目前的素數的名單中，all使用它們之前，實際上比這兩個primes1和primes2更快：

primes3 = iterate 
    (\ps -> ([x | 
      x <- [head ps + 1..], 
      all (\p -> x `mod` p /= 0) $ reverse ps] !! 0) 
     : ps) 
    [2] 

primesTo3 :: Integer -> [Integer] 
primesTo3 n = tail $ head $ dropWhile (\p -> head p <= n) primes3 

ghci速度10000作爲參數：

*Main> primesTo3 10000 
... 
(0.41 secs, 241128512 bytes) 

和編譯與ghc -O2：

$ time ./primes3 
... 
./primes 0.05s user 0.00s system 24% cpu 0.209 total 

Answer 2

我知道你說你不是在尋找一個適合Haskell的最佳素數生成器，但是你仍然對「兩個函數的速度差異」感興趣。因此，這裏是你的校正功能，primes3，它通過(:)增加了素數，以相反的順序幾個語法操作，並逆轉它們每一次測試，

primes3 :: [[Integer]] 
primes3 = iterate 
    (\ps -> ([x | 
      x <- [head ps + 1..], 
      all (\p -> x `mod` p /= 0) $ 
       takeWhile (\p-> p*p <= x) $ reverse ps] !! 0) 
     : ps)       -- ^^^^^^^^^^ 
    [2] 

這可以修改代碼（雖然這不會改變效率）：

primes3b :: [[Integer]] 
primes3b = iterate 
    (\ps -> ([x | 
      x <- [head ps + 1..], 
      all (\p -> x `mod` p /= 0) $ 
       takeWhile (\p-> p*p <= x) $ map head $ primes3b ] !! 0) 
     : ps)       -- ^^^^^^^^^^^^^^^^^^^ 
    [2] 

不是嗎？並且，它等效於（注意型變化）

primes4 :: [Integer] 
primes4 = map head $ iterate 
    (\ps -> ([x | 
      x <- [head ps + 1..], 
      all (\p -> x `mod` p /= 0) $ 
       takeWhile (\p-> p*p <= x) primes4 ] !! 0) 
     : ps)       -- ^^^^^^^ 
    [2] 

其是相同

primes5 :: [Integer] 
primes5 = iterate 
    (\p -> head [x | x <- [p + 1..], 
       all (\p -> x `mod` p /= 0) $ 
        takeWhile (\p-> p*p <= x) primes5 ] 
      ) -- nothing! 
    2 

或，有點快，

primes6 :: [Integer] 
primes6 = 2 : iterate 
    (\p -> head [x | x <- [p + 2, p + 4..], 
       all (\p -> x `mod` p /= 0) $ tail $ 
        takeWhile (\p-> p*p <= x) primes6 ]) 
    3   -- ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 

最後，（和具有相當大的增加速度，甚至empirical orders of growth事實證明） - 爲什麼在每次迭代中只添加一個數字，花費了工作來獲取質數以便測試？我們可以通過連續的素數平方之間的部分來工作。所取出的素數列表是這些段的相同長度，以及通過1該長度增加從段到段：

primes7 :: [Integer] 
primes7 = concatMap snd $ iterate 
       (\((n,p:ps@(q:_)),_) -> ((n+1,ps), 
         [x | let lst = take n $ tail primes7, 
          x <- [p*p + 2, p*p + 4..q*q-2], 
          all ((/= 0).rem x) lst])) 
       ((1,tail primes7),[2,3,5,7]) 

這實際上表示最佳試除法篩。