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.

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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