Хаскелл:более быстрое суммирование простых чисел
Вопрос
Отказ от ответственности:Я работаю над задачей Эйлера 9.
Я складываю довольно большие числа, все простые числа от 1 до 2 000 000.
Суммирование этих простых чисел занимает вечность.Я использую встроенную в Haskell функцию sum.
как в:
sum listOfPrimes
Есть ли другие более быстрые варианты?
--Мой основной генератор был медленным звеном в моем коде.
Решение
Похоже, ваша проблема не в суммировании чисел, а в их генерации.Какова ваша реализация listOfPrimes?
Эта статья может быть интересна: http://lambda-the-ultimate.org/node/3127
Другие советы
Я надеюсь, что вы используете 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
Переключаемся на потоки, так что sum .возьми пока предохранители:
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
Я написал «Решето Эратосфена». здесь:
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)
на моем рабочем столе.Могло быть лучше?Конечно, это занимает Дж менее 1 секунды для запуска
+/p:i.p:^:_1]20000000 12272577818052
но у него довольно оптимизированный генератор простых чисел.
Медленная часть вашей функции — это наверняка генерация простых чисел, а не 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
список.Это также довольно быстро, хотя можно было бы провести дальнейшую оптимизацию за счет удобочитаемости.