6

私はHaskellでいくつかの古典的な問題を解決して機能スキルを開発していますが、この「プログラミング実践」サイトで提案されている最適化を実装するのに問題があります。

この問題には3つの解決策があり、3番目の解決策は2番目の解決策に比べて遅すぎます。誰かが私のコードの改善を提案できますか？

私の実装は次のとおりです。

-- primeira implementação
primes n
    | n < 2 = []
    | n == 2 = [2]
    | n `mod` 2 == 0 = primes'
    | otherwise = if (find (\x -> n `mod` x == 0) primes') == Nothing then
                      n:primes'
                  else
                      primes'
    where primes' = primes (n - 1)

-- segunda implementação
primes' :: Integer -> [Integer]
primes' n = sieve $ 2 : [3,5..n]
    where sieve :: [Integer] -> [Integer]
          sieve [] = []
          sieve l@(x:xs)
              | x*x >= n = l
              | otherwise = x : sieve list'
              where list' = filter (\y -> y `mod` x /= 0) xs

-- terceira implementação
primes'' :: Integer -> [Integer]
primes'' n = 2 : sieve 3 [3,5..n]
    where sieve :: Integer -> [Integer] -> [Integer]
          sieve _ [] = []
          sieve m l@(x:xs)
              | m*m >= n = l
              | x < m*m = x : sieve m xs
              | otherwise = sieve (m + 2) list'
              where list'= filter (\y -> y `mod` m /= 0) l
4

3 に答える 3

6

まず第一に、mod遅いのでrem、それが問題ではない状況で使用します（基本的に、ネガを扱っていないとき）。次に、Criterionを使用して、何がより高速で、どの変更が実際に最適化されているかを（自分自身に）示します。私はこれであなたの質問に完全な答えを与えていないことを知っていますが、あなた（そして他の潜在的な回答者）が始めるのに良い場所なので、ここにいくつかのコードがあります：

import List
import Criterion.Main

main = do
  str <- getLine
  let run f = length . f
      input = read str :: Integer
  defaultMain   [ bench "primes" (nf (run primes) input)
                , bench "primes'" (nf (run primes') input)
                , bench "primes''" (nf (run primes'') input)
                , bench "primesTMD" (nf (run primesTMD) input)
                , bench "primes'TMD" (nf (run primes'TMD) input)
                , bench "primes''TMD" (nf (run primes''TMD) input)
                ]
  putStrLn . show . length . primes'' $ (read str :: Integer)

-- primeira implementação
primes n
    | n < 2 = []
    | n == 2 = [2]
    | n `mod` 2 == 0 = primes'
    | otherwise = if (find (\x -> n `mod` x == 0) primes') == Nothing then
                      n:primes'
                  else
                      primes'
    where primes' = primes (n - 1)

primesTMD n
    | n < 2 = []
    | n == 2 = [2]
    | n `mod` 2 == 0 = primes'
    | otherwise = if (find (\x -> n `rem` x == 0) primes') == Nothing then
                      n:primes'
                  else
                      primes'
    where primes' = primesTMD (n - 1)

-- segunda implementação
primes' :: Integer -> [Integer]
primes' n = sieve $ 2 : [3,5..n]
    where sieve :: [Integer] -> [Integer]
          sieve [] = []
          sieve l@(x:xs)
              | x*x >= n = l
              | otherwise = x : sieve list'
              where list' = filter (\y -> y `mod` x /= 0) xs

primes'TMD :: Integer -> [Integer]
primes'TMD n = sieve $ 2 : [3,5..n]
    where sieve :: [Integer] -> [Integer]
          sieve [] = []
          sieve l@(x:xs)
              | x*x >= n = l
              | otherwise = x : sieve list'
              where list' = filter (\y -> y `rem` x /= 0) xs

-- terceira implementação
primes'' :: Integer -> [Integer]
primes'' n = 2 : sieve 3 [3,5..n]
    where sieve :: Integer -> [Integer] -> [Integer]
          sieve _ [] = []
          sieve m l@(x:xs)
              | m*m >= n = l
              | x < m*m = x : sieve m xs
              | otherwise = sieve (m + 2) list'
              where list'= filter (\y -> y `mod` m /= 0) l

primes''TMD :: Integer -> [Integer]
primes''TMD n = 2 : sieve 3 [3,5..n]
    where sieve :: Integer -> [Integer] -> [Integer]
          sieve _ [] = []
          sieve m l@(x:xs)
              | m*m >= n = l
              | x < m*m = x : sieve m xs
              | otherwise = sieve (m + 2) list'
              where list'= filter (\y -> y `rem` m /= 0) l

以下を使用して、バリアントの実行時間が改善されていることに注目してくださいrem。

 $ ghc --make -O2 sieve.hs
 $./sieve
 5000
 ...
 benchmarking primes 
 mean: 23.88546 ms, lb 23.84035 ms, ub 23.95000 ms

 benchmarking primes'
 mean: 775.9981 us, lb 775.4639 us, ub 776.7081 us

 benchmarking primes''
 mean: 837.7901 us, lb 836.7824 us, ub 839.0260 us

 benchmarking primesTMD
 mean: 16.15421 ms, lb 16.11955 ms, ub 16.19202 ms

 benchmarking primes'TMD
 mean: 568.9857 us, lb 568.5819 us, ub 569.4641 us

 benchmarking primes''TMD
 mean: 642.5665 us, lb 642.0495 us, ub 643.4105 us

あなたがあなた自身の教育のためにこれをしているのを見ますが、Haskell.orgのPrimesとハッキングの速いPrimesパッケージの関連リンクに注目する価値があります。

于 2010-10-04T04:39:43.997 に答える
6

3番目のリビジョンの問題は、ふるいにかける次の要素をどのように選択するかということだと私には思えます。無差別に2ずつインクリメントします。問題は、不要な数をふるいにかけることです。たとえば、このバージョンでは、最終的に9をmとして渡すことになり、リストに含まれていなくても9をフィルタリングするために追加の再帰を実行するため、これを選択する必要はありません。そもそも（3の最初のフィルターで削除されているため）

2番目のバージョンは、ふるいにかける数の2乗を超えてフィルタリングを開始しませんが、不要なふるい分け値を選択することはありません。

言い換えれば、あなたは3とnの間のすべての奇数をふるいにかけることになると思います。代わりに、前のパスでまだ削除されていないすべての奇数をふるいにかける必要があります。

現在のふるいの値の2乗でふるいを開始する最適化を正しく実装するには、リストの前を保持しながら、後ろに要素が含まれるふるいにかける必要があります>=ふるいの値の2乗。これにより、連結を使用せざるを得なくなると思います。++を使用することによって生じるオーバーヘッドを相殺するのに、最適化が十分に適切かどうかはわかりません。

于 2010-10-04T05:29:29.520 に答える
1

これは最適化されていませんが、表現力豊かな実装です 。haskellのエラトステネスのふるいのビデオをチェックしてください

import qualified Data.Set as Set(fromList,difference)
kr n l = (*n) <$> [2..l `div` n]
g n = difference (fromList [2..n]) (fromList $ concat $ ((flip kr) n) <$> [2..n])
于 2020-10-18T19:02:23.923 に答える