haskell - Haskell:素数のより高速な合計

Question

免責事項: 私はオイラー問題 9 に取り組んでいます。

1 から 2 000 000 までのすべての素数を、いくつかのかなり大きな数を合計しています。

これらの素数を合計すると、永遠にかかります。関数「sum」に組み込まれているhaskellを使用しています。

次のように:

sum listOfPrimes

他に高速なオプションはありますか?

--私のプライム ジェネレーターは、コード内の低速リンクでした。

Answer 1

問題は数値を合計するのではなく、数値を生成することのようです。listOfPrimesの実装は何ですか？

この論文は興味深いかもしれません：http：//lambda-the-ultimate.org/node/3127

Answer 2

ghciではなくghc-O2を使用しているといいのですが。あなたの問題は、総和ではなく、世代にあります。

より高速な方法の1つは、ストリーム融合ベースのシーケンスを使用することです。これにより、最適化が向上します。通常のリストの場合：

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

Answer 3

私はここに「エラトステネスのふるい」を書きました：

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秒かかります。もっとよくなるはず？確かに、実行には1秒未満のJが必要です

   + / p：ip：^：_1] 20000000
12272577818052

しかし、それはかなり最適化された素数ジェネレーターを持っています。

Answer 4

関数の遅い部分は、関数ではなく素数の生成です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リストの再帰と遅延を使用するため、まったく機能することに少し驚くかもしれません。また、読みやすさを犠牲にしてさらに最適化を行うこともできますが、かなり高速です。