Haskell:素数的快速求和

Question

免责声明:我正在研究欧拉问题9.

我加了一些相当大的数字,所有的素数从1到2 000 000.

总结这些素数需要永远.我正在使用内置函数'sum'的haskell.

如:

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

切换到流,所以总和.takeHhile保险丝:

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

我在这里写了一篇"Eratosthenes的筛子" :

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秒.有待改善？当然,需要J不到1秒才能运行

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

但它有一个非常优化的素数发生器.

Answer 4

函数的缓慢部分是确保生成素数而不是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列表的递归和懒惰.它也相当快,但可以进一步优化而牺牲可读性.