Haskell: plus rapide somme des nombres premiers
Question
Disclaimer:. Je travaille sur Euler Problème 9
J'ajoute quelques chiffres assez grands, tous les nombres premiers 1 à 2 000 000
Résumant ces nombres premiers prend une éternité. J'utilise la haskell fonction intégrée « somme ».
comme dans:
sum listOfPrimes
Y at-il d'autres plus rapides options?
- Mon premier générateur était le lien lent dans mon code.
La solution
Il semble que votre problème n'est pas la somme des chiffres, mais les générer. Qu'est-ce que votre implémentation de listOfPrimes?
Le présent document peut être intéressant: http://lambda-the-ultimate.org/ node / 3127
Autres conseils
J'espère que vous utilisez -O2 GHC et non ghci, non? Votre problème sera dans la génération, et non pas la somme.
Un moyen plus rapide consiste à utiliser des séquences à base de fusion-courant, qui optimisent mieux. Avec les listes régulières:
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))
Nous obtenons,
$ ghc -O2 --make A.hs
$ time ./A
142913828922
./A 9.99s user 0.17s system 99% cpu 10.166 total
Changement de flux, de sorte que la somme. fusibles takeWhile:
import qualified Data.List.Stream as S
main = print (S.sum (S.takeWhile (<= 2000000) primes))
Enregistre un petit temps,
$ time ./A
142913828922
./A 9.60s user 0.13s system 99% cpu 9.795 total
Mais votre problème sera génération de choix, comme on peut le voir si nous rejetons la somme tout à fait, en remplaçant la somme avec la dernière:
$ time ./A
1999993
./A 9.65s user 0.12s system 99% cpu 9.768 total
Donc, trouver un générateur meilleur premier. : -)
Enfin, il y a une bibliothèque pour les générateurs Hackage premiers rapides:
http: // hackage.haskell.org/packages/archive/primes/0.1.1/doc/html/Data-Numbers-Primes.html
Utilisation, notre temps devient:
$ 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
J'ai écrit un "Crible d'Eratosthène" :
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
Avec cela, il faut environ 25s à print . sum $ takeWhile (<= 20000000)
sur mon bureau. Cela pourrait être mieux? Bien sûr, il faut J moins de 1 seconde pour exécuter
+/p:i.p:^:_1]20000000 12272577818052
mais il a un générateur de nombres premiers assez optimisé.
La partie lente de votre fonction est sûre la génération des nombres premiers, et non la fonction sum
. Une belle façon de générer des nombres premiers serait:
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..]
Je pense qu'il est très facile à lire, mais peut-être un peu surprenant que cela fonctionne du tout parce qu'il utilise la récursivité et la paresse de la liste des primes
. Il est également assez rapide, bien que l'on pourrait faire d'autres optimisations au détriment de la lisibilité.