Haskell: la suma de los números primos más rápido
Pregunta
exención de responsabilidad:. Estoy trabajando en el problema 9 Euler
Estoy sumando algunas bastante grandes números, todos los números primos desde 1 hasta 2 000 000.
En resumen esos números primos toma siempre. Estoy usando el Haskell construido en función de 'suma'.
como en:
sum listOfPrimes
¿Hay otras opciones más rápidas?
- Mi primer generador fue el enlace lento en mi código.
Solución
Parece que su problema no es la suma de los números, sino generarlos. ¿Cuál es su aplicación de listOfPrimes?
Este papel puede ser de interés: http://lambda-the-ultimate.org/ nodo / 3127
Otros consejos
Espero que esté utilizando O2 GHC y no ghci, ¿verdad? Su problema será en la generación, no la suma.
Una manera más rápida es usar secuencias basadas en fusión de transmisión, que optimizan mejor. Con las 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))
Obtenemos,
$ ghc -O2 --make A.hs
$ time ./A
142913828922
./A 9.99s user 0.17s system 99% cpu 10.166 total
El cambio a los arroyos, por lo que suma. takeWhile fusiona:
import qualified Data.List.Stream as S
main = print (S.sum (S.takeWhile (<= 2000000) primes))
ahorra algo de tiempo pequeño,
$ time ./A
142913828922
./A 9.60s user 0.13s system 99% cpu 9.795 total
Sin embargo, su problema será primer generación, como podemos ver si descartamos la suma total, en sustitución de suma con el pasado:
$ time ./A
1999993
./A 9.65s user 0.12s system 99% cpu 9.768 total
Así que encontrar un generador mejor primo. : -)
Por último, hay una biblioteca en Hackage de los principales generadores rápidos:
http: // hackage.haskell.org/packages/archive/primes/0.1.1/doc/html/Data-Numbers-Primes.html
Con ella, se convierte en nuestro tiempo:
$ 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
Me escribió una "criba de Eratóstenes" aquí :
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
El uso de este, se tarda unos 25 años a print . sum $ takeWhile (<= 20000000)
en mi escritorio. ¿Podría ser mejor? Claro, se necesita J menos de 1 segundo para ejecutar
+/p:i.p:^:_1]20000000 12272577818052
pero tiene un generador de números primos muy optimizado.
La parte lenta de la función es segura la generación de los números primos, no la función sum
. Una buena manera de generar números primos sería:
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..]
Creo que es muy fácil de leer, aunque quizás un poco sorprendente que funciona en absoluto, ya que utiliza la recursividad y la pereza de la lista primes
. También es bastante rápido, aunque se podría hacer optimizaciones adicionales a expensas de la legibilidad.