ハスケル：素数の速い合計

StackOverflow https://stackoverflow.com/questions/1139953

  •  16-09-2019
  •  | 
  •  

質問

免責事項：私はオイラーの問題に取り組んでいる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は、読みやすさを犠牲にしてさらなる最適化を行うことができても、それは、またかなり高速です。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top