免责声明:我正在研究欧拉问题 9。
我将一些相当大的数字相加,从 1 到 2 000 000 的所有素数。
对这些素数求和需要很长时间。我正在使用内置函数“sum”的haskell。
如:
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 。takeWhile 熔断器:
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
但是您的问题将是素数生成,因为我们可以看到我们是否完全丢弃总和,将 sum 替换为 last:
$ 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
print . sum $ takeWhile (<= 20000000)
使用它,在我的桌面上大约需要 25 秒。有待改善?当然,运行需要不到 1 秒的J
+/p:ip:^:_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
列表的递归和惰性。它也相当快,尽管可以以牺牲可读性为代价进行进一步的优化。