Haskell: la suma de los números primos más rápido

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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.