6

そこで、私は素数を遅延生成する方法に取り組んでいました。これらの 3 つの定義を思いつきました。これらはすべて同等の方法で機能します。つまり、新しい整数のそれぞれが先行するすべての素数の因数を持っているかどうかをチェックするだけです。

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）、新しいプライム。primes1f_ = f (const True)

非科学的なテスト (ghci で実行) から見ると、よりも高速に実行take 1000されるようです。primes3primes2

このことから教訓を得て、関数を配列の操作として表現できる場合、効率のために後者の方法で実装する必要があると仮定する必要がありますか、それともここで何か他のことが起こっているのでしょうか?

4

2 に答える 2

9

の 2 番目の引数は何に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 を構築するオーバーヘッドは、 eachf :: Integer -> ... -> Boolを構築するオーバーヘッドよりも大幅に高くなる可能性があります。ps :: [Integer]f ... xall ... 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]}
...

マップは、足し算だけを使用して、将来の倍数を追跡します。

于 2009-05-22T16:29:01.643 に答える
1

に変更するprimes3ことでより効率的にできることに注意してください。ランニングは、左引数の長さは線形ですが、右引数の長さは一定です。ps++[x](x:ps)(++)

于 2009-05-22T19:52:46.157 に答える