Haskell: более быстрое суммирование простых чисел

Question

Отказ от ответственности: я работаю над проблемой Эйлера 9.

Я складываю довольно большие числа, все простые числа от 1 до 2 000 000.

Суммирование этих простых чисел занимает вечность. Я использую встроенную функцию haskell 'sum'.

как в:

sum listOfPrimes

Есть ли другие более быстрые варианты?

- Мой основной генератор был медленной ссылкой в ​​моем коде.

Answer 1

Похоже, ваша проблема не в суммировании чисел, а в их генерации. Какова ваша реализация listOfPrimes?

Этот документ может представлять интерес: http://lambda -the-ultimate.org / node / 3127

Answer 2

Я надеюсь, что вы используете ghc -O2, а не ghci, верно? Ваша проблема будет в поколении, а не в суммировании.

Одним из более быстрых способов является использование потоковых последовательностей на основе слияния, которые лучше оптимизируются. С обычными списками:

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))

Получим,

$ ghc -O2 --make A.hs
$ time ./A           
142913828922
./A  9.99s user 0.17s system 99% cpu 10.166 total

Переключение на потоки, поэтому сумма. взять предохранители:

import qualified Data.List.Stream as S
main = print (S.sum (S.takeWhile (<= 2000000) primes))

Экономит немного времени,

$ time ./A           
142913828922
./A  9.60s user 0.13s system 99% cpu 9.795 total

Но ваша проблема будет в генерации простых чисел, как мы видим, если мы отбросим суммирование вообще, заменив сумму на последнюю:

$ time ./A           
1999993
./A  9.65s user 0.12s system 99% cpu 9.768 total

Так что найдите лучший основной генератор. : -)

Наконец, в Hackage есть библиотека для быстрых простых генераторов:

http://hackage.haskell.org/packages/archive/primes/0.1.1/doc/html/Data-Numbers-Primes.html

Используя его, наше время становится:

$ 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

Медленная часть вашей функции - это, конечно, генерация простых чисел, а не функция sum. Хороший способ генерирования простых чисел:

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

Я думаю, что это очень читабельно, хотя, может быть, немного удивительно, что оно работает вообще, потому что использует рекурсию и лень из списка primes. Это также довольно быстро, хотя можно сделать дальнейшую оптимизацию за счет читабельности.

Answer 4

Я написал «Сито Эратосфена» здесь :

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

На этом рабочем столе требуется около 25 с до print . sum $ takeWhile (<= 20000000). Могло быть лучше? Конечно, для запуска

требуется J менее чем за 1 секунду

   +/p:i.p:^:_1]20000000
12272577818052

но у него довольно оптимизированный генератор простых чисел.