質問
免責事項:私はオイラーの問題に取り組んでいる9
私はかなり大きな数、すべての素数1から2 000 000までを加算しています。
これらの素数を合計永遠にかかります。私は、関数「合計」内に構築されたHaskellのを使用しています。
のように:
sum listOfPrimes
他の高速化オプションはありますか?
- マイプライム発電機は私のコードで低速リンクでした。
解決
それはあなたの問題は数字を合計し、それらを生成していないように聞こえます。 listOfPrimesの実装は何ですか?
この論文は、興味のある: http://lambda-the-ultimate.org/ノード/ 3127 の
他のヒント
私は、あなたが右、GHCiのGHC -O2を使用していません願っていますか?あなたの問題は、世代、ない合計になります。
一つのより高速な方法は、より良い最適化ストリームの融合ベースのシーケンスを、使用することです。通常のリストの場合:
import Data.List
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
-- fuse:
main = print (sum (takeWhile (<= 2000000) primes))
私たちが得る、
$ ghc -O2 --make A.hs
$ time ./A
142913828922
./A 9.99s user 0.17s system 99% cpu 10.166 total
ストリームへの切り替え、その合計。 takeWhileが融合します:
import qualified Data.List.Stream as S
main = print (S.sum (S.takeWhile (<= 2000000) primes))
いくつかの小さな時間を節約、
$ time ./A
142913828922
./A 9.60s user 0.13s system 99% cpu 9.795 total
しかし、我々は完全に和を破棄した場合、我々は最後に合計を交換し、見ることができるようにあなたの問題は、素数生成されます。
$ time ./A
1999993
./A 9.65s user 0.12s system 99% cpu 9.768 total
だから、より良いプライム発電機を見つけます。 : - )
最後に、速いプライム発電用Hackage上のライブラリがあります:
HTTP:// hackage.haskell.org/packages/archive/primes/0.1.1/doc/html/Data-Numbers-Primes.htmlする
それを使用して、私たちの時間となります:
$ cabal install primes
$ cabal install stream-fusion
$ cat A.hs
import qualified Data.List.Stream as S
import Data.Numbers.Primes
main = print . S.sum . S.takeWhile (<= 2000000) $ primes
$ ghc -O2 -fvia-C -optc-O3 A.hs --make
$ time ./A
142913828922
./A 0.62s user 0.07s system 99% cpu 0.694 total
私はここを "ふるいエラトステネスの" を書いてます:
import Data.List
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
これを使用して、それは私のデスクトップ上print . sum $ takeWhile (<= 20000000)
する25秒ほどかかります。もっとよくなるはず?確かに、それはとり J実行するにはの1秒未満
+/p:i.p:^:_1]20000000 12272577818052
それはかなり最適化された素数生成器を持っています。
あなたの関数の遅い部分は確かに素数の生成、ないsum
機能です。素数を生成するための良い方法は以下のようになります:
isprime :: (Integral i) => i -> Bool
isprime n = isprime_ n primes
where isprime_ n (p:ps)
| p*p > n = True
| n `mod` p == 0 = False
| otherwise = isprime_ n ps
primes :: (Integral i) => [i]
primes = 2 : filter isprime [3,5..]
私はそれがprimes
リストの再帰と怠惰を使用していますので、それがすべてで動作することを多分少し意外なものの、それは、非常に読みやすいと思います。 1は、読みやすさを犠牲にしてさらなる最適化を行うことができても、それは、またかなり高速です。