问Haskell:更快的素数求和
EN

Stack Overflow用户

提问于 2009-07-16 12:04:25

回答 3查看 3.2K关注 0票数 4

免责声明:我正在处理Euler问题9。

我把一些很大的数字加起来，所有的素数都是从1到2000 000。

把这些素数加起来需要永远的时间。我使用了haskell内置的函数'sum‘。

如下所示：

sum listOfPrimes

还有没有其他更快的选择？

--我的主生成器是我代码中的慢链接。

haskell

primes

回答 3

Stack Overflow用户

回答已采纳

发布于 2009-07-16 12:09:31

听起来你的问题不是对数字求和，而是生成它们。您对listOfPrimes的实现是什么？

这篇论文可能会引起人们的兴趣：http://lambda-the-ultimate.org/node/3127

票数 11

Stack Overflow用户

发布于 2009-07-16 12:54:04

我希望你使用的是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

切换到streams，所以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

但是您的问题将是素数生成，正如我们可以看到的那样，如果我们完全丢弃求和，用last替换sum：

$ 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

票数 9

Stack Overflow用户

发布于 2009-07-16 15:32:15

你的函数中最慢的部分肯定是素数的生成，而不是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..]