Haskell: soma mais rápido dos números primos
Pergunta
Disclaimer:. Eu estou trabalhando em Euler Problema 9
Eu estou adicionando-se algumas bastante grandes números, todos os números primos 1-2 000 000
Somando esses números primos leva uma eternidade. Eu estou usando o Haskell construído em função de 'soma'.
como em:
sum listOfPrimes
Existem outras opções mais rápidas?
- Meu gerador principal era a ligação lenta no meu código.
Solução
Parece que seu problema não é somando os números, mas gerá-los. Qual é a sua implementação de listOfPrimes?
Este documento pode ser de interesse: http://lambda-the-ultimate.org/ node / 3127
Outras dicas
Eu estou esperando que você está usando -O2 ghc e não ghci, certo? Seu problema será na geração, não o somatório.
Uma maneira mais rápida é a sequências de fusão à base de transmissão ao uso, que optimizam a melhor. Com listas regulares:
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))
Recebemos,
$ ghc -O2 --make A.hs
$ time ./A
142913828922
./A 9.99s user 0.17s system 99% cpu 10.166 total
Mudar para córregos, então resumir. fusíveis TakeWhile:
import qualified Data.List.Stream as S
main = print (S.sum (S.takeWhile (<= 2000000) primes))
Salva algum pequeno tempo,
$ time ./A
142913828922
./A 9.60s user 0.13s system 99% cpu 9.795 total
Mas o seu problema será primeiro-geração, como podemos ver se descartar o somatório completamente, substituindo soma com última:
$ time ./A
1999993
./A 9.65s user 0.12s system 99% cpu 9.768 total
Assim, encontrar um gerador melhor prime. : -)
Finalmente, há uma biblioteca no Hackage para geradores rápido principais:
http: // hackage.haskell.org/packages/archive/primes/0.1.1/doc/html/Data-Numbers-Primes.html
Com ele, nosso tempo torna-se:
$ 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
Eu escrevi um "Crivo de Eratóstenes" aqui :
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
Usando isso, ele leva cerca de 25s para print . sum $ takeWhile (<= 20000000)
no meu desktop. Poderia ser melhor? Claro, é preciso J menos de 1 segundo para executar
+/p:i.p:^:_1]20000000 12272577818052
mas tem um gerador de número primo bastante otimizado.
A parte lenta da sua função é certa a geração dos números primos, não a função sum
. Uma boa maneira de gerar números primos seria:
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..]
Eu acho que é muito legível, embora talvez um pouco surpreendente que ele funciona em todos, porque ele usa recursão e preguiça da lista primes
. É também bastante rápido, embora um poderia fazer otimizações adicionais em detrimento da legibilidade.