Haskell: più veloce somma dei numeri primi
Domanda
Disclaimer:. Sto lavorando su Euler Problema 9
Sto aggiungendo alcune piuttosto grandi numeri, tutti i numeri primi 1-2 000 000
In sintesi questi numeri primi prende per sempre. Sto utilizzando il haskell costruito in funzione 'sum'.
come in:
sum listOfPrimes
Ci sono altre opzioni più veloci?
- Il mio generatore primario era il collegamento lento nel mio codice.
Soluzione
Sembra che il tuo problema non è sommando i numeri, ma li genera. Qual è l'implementazione di listOfPrimes?
Questo documento può essere di interesse: http://lambda-the-ultimate.org/ node / 3127
Altri suggerimenti
Spero che si sta utilizzando -O2 ghc e non ghci, giusto? Il tuo problema sarà nella generazione, non la sommatoria.
Un modo più veloce è quello di utilizzare le sequenze di fusione a base di flusso, che ottimizzano meglio. Con le liste regolari:
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))
Si arriva,
$ ghc -O2 --make A.hs
$ time ./A
142913828922
./A 9.99s user 0.17s system 99% cpu 10.166 total
Il passaggio a corsi d'acqua, in modo somma. TakeWhile fonde:
import qualified Data.List.Stream as S
main = print (S.sum (S.takeWhile (<= 2000000) primes))
Salva qualche piccolo tempo,
$ time ./A
142913828922
./A 9.60s user 0.13s system 99% cpu 9.795 total
Ma il vostro problema sarà primo generazione, come possiamo vedere se noi scartare la somma del tutto, sostituendo somma allo scorso:
$ time ./A
1999993
./A 9.65s user 0.12s system 99% cpu 9.768 total
Quindi, trovare un generatore di meglio primaria. : -)
Infine, c'è una biblioteca su Hackage per i generatori principali veloci:
http: // hackage.haskell.org/packages/archive/primes/0.1.1/doc/html/Data-Numbers-Primes.html
Con esso, il nostro tempo diventa:
$ 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
ho scritto un "crivello di Eratostene" qui :
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
Con questo, ci vogliono circa 25 anni per print . sum $ takeWhile (<= 20000000)
sul mio desktop. Potrebbe essere migliore? Certo, ci vuole J meno di 1 secondo per eseguire
+/p:i.p:^:_1]20000000 12272577818052
ma ha un generatore di numeri primi abbastanza ottimizzato.
La parte lenta della vostra funzione è di sicuro la generazione dei numeri primi, non la funzione sum
. Un bel modo per generare numeri primi potrebbe essere:
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..]
Credo che sia molto leggibile, anche se forse un po 'sorprendente che funziona a tutti perché utilizza la ricorsione e la pigrizia della lista primes
. E 'anche piuttosto veloce, anche se si potrebbe fare ulteriori ottimizzazioni a scapito di leggibilità.