6

所以我正在研究一种懒惰地生成素数的方法，我想出了这三个定义，它们都以等效的方式工作 - 只是检查每个新整数是否在所有前面的素数中都有一个因子：

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.

我是否应该从中吸取教训，并假设如果我可以将函数表示为数组上的操作，我应该以后一种方式实现它以提高效率，还是这里发生了其他事情？

4

2 回答 2

9

的第二个参数是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
...

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

运行时编译有时可以为您带来显着的效率提升，但通常会以增加压力和降低生产力为代价，让您几乎一无所获。

在您的情况下，构造 each 的开销可能f :: Integer -> ... -> Bool明显高于构造 each 的开销，ps :: [Integer]调用f ... x与all ... ps.

要从无限的素筛中挤出循环，请摆脱对mod! 整数乘法、除法和取模比整数加法和减法要慢得多。-O2在我的机器上，当计算前 1000 个素数（GHC 6.10.3 ）时，这个实现的时钟速度快了 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]}
...

该地图只使用加法来跟踪未来的倍数。

于 2009-05-22T16:29:01.643 回答
1

请注意，primes3可以通过更改ps++[x]为 来提高效率(x:ps)。运行(++)在其左参数的长度上是线性的，但在右参数的长度上是恒定的。

于 2009-05-22T19:52:46.157 回答