Haskell vs C速度:Eratosthenes的筛子

Question

haskell One使用优化数据实现。但是，尽管Haskell代码已经针对偶数案例进行了优化，但N = 20000的速度差为15倍（以前30倍）。我想知道/为什么我在Haskell中的实施不完美。

原始Haskell

primesUpTo :: Int -> [Int]
primesUpTo n = 2 : put S.empty [3,5..n]
    where put :: S.IntSet -> [Int] -> [Int]
          put _ [] = []
          put comps (x:xs) =
            if S.member x comps
            then put comps xs
            else x : put (S.union comps multiples) xs
                where multiples = S.fromList [x*2, x*3 .. n]

更新

fromDistinctAscList可提高4倍的速度。2-3-5-7-轮升高了50％。

primesUpTo :: Int -> [Int]
primesUpTo n = 2 : 3 : 5 : 7 : put S.empty (takeWhile (<=n) (spin wheel 11))
    where put :: S.IntSet -> [Int] -> [Int]
          put _ [] = []
          put comps (x:xs) =
            if S.member x comps
            then put comps xs
            else x : put (S.union comps multiples) xs
                where multiples = S.fromDistinctAscList [x*x, x*(x+2) .. n]
          spin (x:xs) n = n : spin xs (n + x)
          wheel = 2:4:2:4:6:2:6:4:2:4:6:6:2:6:4:2:6:4:6:8:4:2:4:2:4:8:6:4:6:2:4:6:2:6:6:4:2:4:6:2:6:4:2:4:2:10:2:10:wheel

基准测试

所有时间都通过 *nix time命令，真实空间

测量

Haskell original : 2e6: N/A;    2e7: >30s
Haskell optimized: 2e6: 0.396s; 2e7: 6.273s
C++ Set (ordered): 2e6: 4.694s; 2e7: >30s
C++ Bool Array   : 2e6: 0.039s; 2e7: 0.421s

HASKELL优化比C Bool慢10〜15倍，并且比C 设置的速度快。

。

源代码

C编译器选项：G 5.3.1，g++ -std=c++11Haskell选项：GHC 7.8.4，ghc

c代码（布尔数组）http://pastebin.com/w0s7cswi

 prime[0] = prime[1] = false;
 for (int i=2; i<=limit; i++) { //edited
     if (!prime[i]) continue;
     for (int j=2*i; j<=n; j+=i)
        prime[j] = false;
 }

C代码（SET）http://pastebin.com/snpghru4

 nonprime.insert(1);
 for (int i=2; i<=limit; i++) { //edited
     if (nonprime.count(i) > 0) continue;
     for (int j=2*i; j<=n; j+=i)
        nonprime.insert(j);
 }

Haskell代码http://pastebin.com/humqwvrw代码如上所述。

Answer 1

我想知道/为什么我在Haskell中的实施不完美。

而不是fromList，您最好使用fromDistinctAscList线性。您也可以添加仅奇数倍数以x*x而不是x*2开头，因为所有较小的奇数倍数已经添加。在样式方面，正确的折叠可能比递归更合适。

这样做，我获得了等于2,000,000的n的3倍以上：

import Data.IntSet (member, union, empty, fromDistinctAscList)
sieve :: Int -> [Int]
sieve n = 2: foldr go (const []) [3,5..n] empty
    where
    go i run obs
        | member i obs = run obs
        | otherwise    = i: run (union obs inc)
        where inc = fromDistinctAscList [i*i, i*(i + 2)..n]

尽管如此，一个数组同时具有O（1）访问权限和 CACHERYER友好内存分配。使用可变的阵列，我看到的是您的Haskell代码的15倍以上的性能（再次等于2,000,000）：

{-# LANGUAGE FlexibleContexts #-}
import Data.Array.ST (STUArray)
import Control.Monad (forM_, foldM)
import Control.Monad.ST (ST, runST)
import Data.Array.Base (newArray, unsafeWrite, unsafeRead)
sieve :: Int -> [Int]
sieve n = reverse $ runST $ do
    arr <- newArray (0, n) False :: ST s (STUArray s Int Bool)
    foldM (go arr) [2] [3,5..n]
    where
    go arr acc i = do
        b <- unsafeRead arr i
        if b then return acc else do
            forM_ [i*i, i*(i + 2).. n] $ k -> unsafeWrite arr k True
            return $ i: acc