ハスケルスタイル/効率

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 

だから、それは私がが素数の数 私たちのオーダーの作業が必要だと思うた（すべての整数を f_ = f (const True)を再計算回避するのでprimes2が、primes1より少し速くする必要があります私には思えます今までに見つかった）、encしたときにのみ更新されます新しい素数を得なさい。

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

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

Answer 1

fの第2引数は何のために必要ですか？私の意見では、これらの選択肢の両方が戻って質問に、とにかく

---

...読みやすくしており、大幅にパフォーマンスに影響を与えません。場合によっては、関数をデータ構造として使用することは、特定のタスクの最適な表現であり、時にはそうでない場合もあります。コーディングの容易さとパフォーマンスの点で "最高"の点で "ベスト"は必ずしも同じものではありません。 「データ構造として機能する」技術がruntime compilationに不可欠ですが、そのページには警告しているとして、ランタイムのコンパイルはあなたに重要な効率向上を時々勝つことができるが、多くの場合、あなたのストレスの増加のコストであなたにほとんど何も勝つことはできません

生産性が低下します。あなたのケースでは

、それは各f :: Integer -> ... -> Boolを構築するオーバーヘッドがall ... ps対f ... xを呼び出すときにほとんど、あるいはまったく違いで、各ps :: [Integer]を構築するオーバーヘッドよりも有意に高いことが考えられます。

---

modへの呼び出しを取り除くため、無限プライムふるいのうちのサイクルを圧迫します！整数の乗算、除算、および係数は、整数の加算および減算よりもはるかに低速です。私のマシンでは、この実装は最初の1000素数（GHC 6.10.3 -O2）を計算すると40％速くなります。 （JSON風の構文のビットを使用して）アクションで

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 

、

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

ps++[x]を(x:ps)に変更すると、primes3をより効率的にすることができます。実行中の(++)は、左の引き数の長さは線形ですが、右の引き数の長さは定数です。