哈斯克尔风格/效率

Question

所以我工作的一种方式懒洋洋地生成素数，我想出了这三个定义，这在同等方式，所有的工作 - 只是检查是否每一个新的整数 具有所有前述的素数之间的一个因素：

primes1 :: [Integer]
primes1 = mkPrimes id [2..]
  where mkPrimes f (x:xs) = 
          if f (const True) x 
          then 
            let g h y = y `mod` x > 0 && h y in
            x : mkPrimes (f . g) xs
          else
            mkPrimes f xs

primes2 :: [Integer]
primes2 = mkPrimes id (const True) [2..]
  where mkPrimes f f_ (x:xs) = 
          if f_ x 
          then 
            let g h y = y `mod` x > 0 && h y in
            x : mkPrimes (f . g) ( f $ g $ const True) xs
          else
            mkPrimes f f_ xs

primes3 :: [Integer]
primes3 = mkPrimes [] [2..]
  where mkPrimes ps (x:xs) = 
          if all (\p -> x `mod` p > 0) ps
          then 
            x : mkPrimes (ps ++ [x]) xs
          else
            mkPrimes ps xs

所以，在我看来primes2应该比primes1快一点，因为它避免了重复计算 f_ = f (const True)用于每个整数（我认为需要的数量的数量级上工作 素数我们迄今发现的），只有当我们遇到一个新的主要更新它。

距离不科学试验（运行在ghci中take 1000）好像primes3运行速度更快 比primes2。

我应该从这个教训，假设，如果我可以代表功能作为操作 在阵列上，我应该实现它在效率后者方式，或者是有什么 否则会在这里？

Answer 1

什么是第二个参数的所需f？在我看来，这两种选择的是更具可读性，而且不显著影响性能...

...
            let g y = f y && y `mod` x > 0 in
            x : mkPrimes g xs
...

import Control.Arrow  -- instance Monad (-> r)
import Control.Monad  -- liftM2
(.&&.) = liftM2 (&&)
...
            let g y = y `mod` x > 0 in
            x : mkPrimes (f .&&. g) xs
...

---

总之，回到问题。有时使用功能为数据结构是一定任务的最佳表现，有时不是。 “最佳”，在易用性，编码的术语和“最好”在性能方面并不总是相同的事情。的“作为数据结构”的技术是运行时编译必需的，但作为该网页警告，

  

运行时编译有时会为你赢得显著提高效率，但往往能赢得你在你的压力增加和生产率降低的成本几乎没有。

在你的情况，很可能是构成每个f :: Integer -> ... -> Bool的开销比调用ps :: [Integer]与f ... x当构建每个all ... ps，很少或根本没有差别的开销显著较高。

---

要挤周期出无限的黄金筛，摆脱调用mod的！整数乘法，除法和模数比整数加法和减法慢得多。在我的机器，在40％该实施方式中的时钟更快的计算第一素数1000（GHC 6.10.3 -O2）。当

import qualified Data.Map as M
primes' :: [Integer]
primes' = mkPrimes 2 M.empty
  where
    mkPrimes n m = case (M.null m, M.findMin m) of
        (False, (n', skips)) | n == n' ->
            mkPrimes (succ n) (addSkips n (M.deleteMin m) skips)
        _ -> n : mkPrimes (succ n) (addSkip n m n)
    addSkip n m s = M.alter (Just . maybe [s] (s:)) (n+s) m
    addSkips = foldl' . addSkip

在动作（使用位JSON肥胖型语法），

   mkPrimes 2 {}
=> 2 : mkPrimes 3 {4: [2]}
=> 2 : 3 : mkPrimes 4 {4: [2], 6: [3]}
=> 2 : 3 : mkPrimes 5 {6: [2, 3]}
=> 2 : 3 : 5 : mkPrimes 6 {6: [2, 3], 10: [5]}
=> 2 : 3 : 5 : mkPrimes 7 {8: [2], 9: [3], 10: [5]}
=> 2 : 3 : 5 : 7 : mkPrimes 8 {8: [2], 9: [3], 10: [5], 14: [7]}
=> 2 : 3 : 5 : 7 : mkPrimes 9 {9: [3], 10: [2, 5], 14: [7]}
=> 2 : 3 : 5 : 7 : mkPrimes 10 {10: [2, 5], 12: [3], 14: [7]}
=> 2 : 3 : 5 : 7 : mkPrimes 11 {12: [2, 3], 14: [7], 15: [5]}
...

地图跟踪将来的倍数，使用只是加法。

Answer 2

请注意primes3可以制成通过改变ps++[x]到(x:ps)更有效。运行(++)处于其左侧参数的长度线性的，但是在恒定右参数的长度。