Оптимизировать код на Haskell, вычисляя сумму всех простых чисел ниже двух миллионов
Задача 10 в проекте Эйлера. Я видел некоторое обсуждение там, но только для C.
Я использовал следующий код для расчета:
print . sum . sieve $ [2..2000000] where
sieve [] = []
sieve (x:xs) = x : sieve (filter ((/= 0) . (`mod` x)) xs)
Это требует возраста, чтобы рассчитать. Мне интересно, есть ли более эффективный способ его расчета?
3 ответа
Многие действительно быстрые способы вычисления простых чисел в haskell описаны на странице haskellwiki для простых чисел. В частности, второй кажется достаточно хорошим, так что вы можете написать это так:
main = print . sum . takeWhile (< 2000000) $ primes
primes = 2: 3: sieve (tail primes) [5,7..]
sieve (p:ps) xs = h ++ sieve ps [x | x <- t, rem x p /= 0]
where (h,~(_:t)) = span (< p*p) xs
Запустив его мы получим:
ghc --make -O2 Euler10.hs
time ./SOAns
142913828922
real 0m1.598s
user 0m1.577s
sys 0m0.017s
В вики описывается, почему ваше решение такое медленное, основная причина в том, что для каждого числа установлено сито до 2000000, когда достаточно одного для каждого простого числа.
Вы можете найти этот документ и последующее обсуждение интересным. Суть в том, что ваш sieve реализация не так эффективна, как "настоящее" сито Эратосфена.
Самый чистый оптимизированный код первичного просеивания, который я лично видел в Haskell, находится в пакете NumberSieves, который включает в себя как традиционное сито, основанное на изменяемых векторах, так и форму сита О'Нила. Не используйте ужасно сложный код в arithmoi пакет - по крайней мере, некоторые из них в настоящее время сломаны и случайным образом вызывают ошибки сегментации.