Haskellのスタイル/効率

Question

だから私は怠惰素数を生成する方法に取り組んでいた、と私は同じ方法ですべての作業はこれら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は、primes1より少し速くする必要があります 私はをすべての整数（のためのf_ = f (const True)はは番号順に作業が必要だと思います 素数の我々は）これまでに見つかった、と私たちは新しい首相が発生した場合にのみ、それを更新しました。

ただ、非科学的なテスト（GHCiの中take 1000を実行している）primes3は速く走るようにそれはそうから primes2よります。

私はこのからのレッスンを取る、と私は運転としての機能を表現することができるかどうかということを前提とすべき 私は効率のために後者の方法でそれを実装する必要があり、または何かがあることは、アレイ、上 ここで起こっ他に？

Answer 1

fのために必要な2番目の引数は何ですか？私の意見では、これらの選択肢の両方がより読みやすくしており、大幅にパフォーマンスに影響を与えない...

...
            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の呼び出しを取り除きます！整数の乗算、除算、および弾性率は、整数加算と減算よりもはるかに遅いです。最初の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]}
...

マップが追加だけを使用していない、将来の倍数を追跡します。

Answer 2

なおprimes3はps++[x]に(x:ps)を変更することにより、より効率的にすることができます。ランニング(++)は、その左側の引数の長さの線形が、右引数の長さが一定である。