performance - 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)对于每个整数(我认为这需要按数字的顺序工作
迄今为止我们发现的质数)，并且仅在遇到新质数时才更新它。

仅根据不科学的测试(在 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
...

无论如何，回到问题。有时使用函数作为数据结构是特定任务的最佳表示，有时则不是。就易于编码而言的“最佳”和就性能而言的“最佳”并不总是一回事。 “作为数据结构的函数”技术对于 runtime compilation 是必不可少的。 ，但正如该页面警告的那样，

Runtime compilation can sometimes win you significant efficiency gains, but can often win you almost nothing at the cost of the your increased stress and reduced productivity.

在您的情况下，构造每个 f :: Integer -> ... -> Bool 的开销很可能是明显高于构造每个 ps :: [Integer] 的开销, 调用 f ... x 时几乎没有区别与 all ... ps 相比.

要从无限质数筛中挤出循环，请去掉对 mod 的调用。 !整数乘法、除法和取模比整数加法和减法要慢得多。在我的机器上，在计算前 1000 个素数(GHC 6.10.3 -O2)时，这个实现的时钟速度快了 40%。

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

该 map 只使用加法来跟踪 future 的倍数。