Haskell风格/效率

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)每个整数(我认为需要按照我们迄今为止找到的素数的顺序工作),并且只在遇到新的时才更新它主要.

仅仅从不科学的测试(take 1000在ghci中运行)看起来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 ... xvs 时几乎没有差别all ... ps.

为了挤出无限素筛的循环,摆脱呼唤mod!整数乘法,除法和模数比整数加法和减法慢得多.在我的机器上,这个实现在计算前1000个素数时速度快40%(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-ish语法),

   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]}
...

地图跟踪未来的倍数,只使用添加.