プロジェクトオイラーの問題10。私はそこにいくつかの議論を見ただけC.Haskellコードを最適化し、200万未満のすべての素数の合計を計算する
のために私は計算するには、次のコードを使用：
print . sum . sieve $ [2..2000000] where
sieve [] = []
sieve (x:xs) = x : sieve (filter ((/= 0) . (`mod` x)) xs)
それは計算に時間がかかります。私はそれを計算するための効率的な方法があれば疑問に思っていますか？
haskellで素数を計算する方法は、多くの場合、haskellwiki page for Prime numbersに記載されています。具体的に二つ目は十分のようですので、あなたはこのようにそれを書くかもしれない：
main = print . sum . takeWhile (< 2000000) $ primes
primes = 2: 3: sieve (tail primes) [5,7..]
sieve (p:ps) xs = h ++ sieve ps [x | x <- t, rem x p /= 0]
where (h,~(_:t)) = span (< p*p) xs
それを実行している我々が得る：
ghc --make -O2 Euler10.hs
time ./SOAns
142913828922
real 0m1.598s
user 0m1.577s
sys 0m0.017s
ソリューションがとても遅いですなぜウィキを説明し、主な理由各素数ごとに1つで十分である2000000までの各数値に対してふるいが設定されていることです。
this paperと続く議論が興味深いかもしれません。要するに、あなたのsieve実装はEratosthenesの '本当の'ふるいほど効率的ではないということです。
私は個人的にHaskellで見てきたクリーン最適化プライムふるいコードが変更可能なベクトルに基づいて、従来のふるいとオニールのふるいの形の両方が含まNumberSievesパッケージ、です。 arithmoiパッケージで恐ろしく複雑なコードを使用しないでください。少なくとも一部は現在破損しており、ランダムにセグメント化エラーが生成されます。
また、typo： 'sieve'の代わりに' seive'があります。 –
が更新されました。ありがとうございました。 – swcai
準線形時間で行うことも可能です（https://stackoverflow.com/questions/44441627/how-to-optimize-this-haskell-code-summing-up-the-primes）。 –