Haskell: schnelle Summierung der Primzahlen

Question

Disclaimer:. Ich arbeite an Euler Problem 9

Ich füge ein paar ziemlich große Zahl, in dem alle Primzahlen von 1 bis 2 000 000

Fasst diese Primzahlen für immer dauert. Ich verwende die Haskell in Funktion ‚Summe‘ gebaut.

, wie in:

sum listOfPrimes

Gibt es noch andere schnelle Optionen?

- Mein bester Generator war die langsame Verbindung in meinem Code.

Answer 1

Es klingt wie Ihr Problem nicht die Zahlen wird summiert, sondern Erzeugen sie. Was ist Ihre Implementierung von listOfPrimes?

Dieses Papier kann von Interesse sein: http://lambda-the-ultimate.org/ node / 3127

Answer 2

Ich hoffe, Sie ghc -O2 und nicht GHCi direkt verwenden? Ihr Problem bei der Erzeugung sein, nicht die Summe.

Ein schneller Weg ist, Strom Fusion-basierten Sequenzen zu verwenden, die besser zu optimieren. Mit regelmäßigen Listen:

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))

Wir bekommen,

$ ghc -O2 --make A.hs
$ time ./A           
142913828922
./A  9.99s user 0.17s system 99% cpu 10.166 total

zu Strömen Switching, so Summe. Takewhile Sicherungen:

import qualified Data.List.Stream as S
main = print (S.sum (S.takeWhile (<= 2000000) primes))

Speichert einige kleine Zeit,

$ time ./A           
142913828922
./A  9.60s user 0.13s system 99% cpu 9.795 total

Aber Ihr Problem wird prime Generation sein, wie wir sehen können, wenn wir die Summe ganz verwerfen, Summe mit letzten ersetzen:

$ time ./A           
1999993
./A  9.65s user 0.12s system 99% cpu 9.768 total

So einen besseren Prime-Generator finden. : -)

Schließlich gibt es eine Bibliothek auf Hackage für schnelle prime Generatoren:

http: // hackage.haskell.org/packages/archive/primes/0.1.1/doc/html/Data-Numbers-Primes.html

Mit ihm unsere Zeit wird:

$ 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

Ich schrieb ein "Sieb des Eratosthenes" hier :

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

Mit diesem, dauert es etwa 25 s auf meinem Desktop print . sum $ takeWhile (<= 20000000). Könnte besser sein? Sicher, es nimmt J unter 1 Sekunde ausführen

   +/p:i.p:^:_1]20000000
12272577818052

, aber es hat einen ziemlich optimierte Primzahl Generator.

Answer 4

Der langsame Teil Ihrer Funktion ist die Erzeugung der Primzahlen sicher, nicht die sum Funktion. Ein schöner Weg, Primzahlen zu erzeugen wäre:

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..]

Ich denke, es ist sehr gut lesbar, wenn auch vielleicht ein wenig überraschend, dass es überhaupt funktioniert, weil es Rekursion und Faulheit der primes Liste verwendet. Es ist auch ziemlich schnell, wenn man auf Kosten der Lesbarkeit weitere Optimierungen tun könnte.