haskell - 对大量数字求和太慢

任务:“对前15,000,000个偶数求和”。

Haskell:

nats = [1..] :: [Int]
evens = filter even nats :: [Int]

MySum:: Int
MySum= sum $ take 15000000 evens

...但是MySum需要很长时间。更准确地说，它比C/C++慢10到20倍。

我发现很多时候，自然编码的Haskell解决方案比C慢10倍左右。我期望GHC是一个非常整洁的优化编译器和任务，这样看起来并不难。

因此，人们可能希望比C慢1.5-2倍。问题出在哪里？

是否可以更好地解决？

这是我正在与以下代码进行比较的C代码:

long long sum = 0;
int n = 0, i = 1;

for (;;) {

  if (i % 2 == 0) {
    sum += i;
    n++;
  }

  if (n == 15000000)
    break;

  i++;
}

编辑1 :我真的知道，它可以在O(1)中进行计算。请抵抗。

编辑2 :我真的知道，偶数是[2,4..]，但是功能even可以是其他O(1)，需要将其实现为一个功能。

最佳答案

列表不是循环
因此，如果将列表用作循环替换，不要感到惊讶，如果循环体很小，您的代码就会变慢。

nats = [1..] :: [Int]
evens = filter even nats :: [Int]

dumbSum :: Int
dumbSum = sum $ take 15000000 evens

sum并不是“好的消费者”，因此GHC尚不能完全消除中间列表。
如果您使用优化进行编译(并且不导出nat)，那么GHC足够聪明，可以将filter与枚举融合在一起，

Rec {
Main.main_go [Occ=LoopBreaker]
  :: GHC.Prim.Int# -> GHC.Prim.Int# -> [GHC.Types.Int]
[GblId, Arity=1, Caf=NoCafRefs, Str=DmdType L]
Main.main_go =
  \ (x_aV2 :: GHC.Prim.Int#) ->
    let {
      r_au7 :: GHC.Prim.Int# -> [GHC.Types.Int]
      [LclId, Str=DmdType]
      r_au7 =
        case x_aV2 of wild_Xl {
          __DEFAULT -> Main.main_go (GHC.Prim.+# wild_Xl 1);
          9223372036854775807 -> n_r1RR
        } } in
    case GHC.Prim.remInt# x_aV2 2 of _ {
      __DEFAULT -> r_au7;
      0 ->
        let {
          wild_atm :: GHC.Types.Int
          [LclId, Str=DmdType m]
          wild_atm = GHC.Types.I# x_aV2 } in
        let {
          lvl_s1Rp :: [GHC.Types.Int]
          [LclId]
          lvl_s1Rp =
            GHC.Types.:
              @ GHC.Types.Int wild_atm (GHC.Types.[] @ GHC.Types.Int) } in
        \ (m_aUL :: GHC.Prim.Int#) ->
          case GHC.Prim.<=# m_aUL 1 of _ {
            GHC.Types.False ->
              GHC.Types.: @ GHC.Types.Int wild_atm (r_au7 (GHC.Prim.-# m_aUL 1));
            GHC.Types.True -> lvl_s1Rp
          }
    }
end Rec }

但这只是GHC的融合所能做到的。您只剩下拳击Int和构建列表单元格。如果给它一个循环，就像给C编译器一样，

module Main where

import Data.Bits

main :: IO ()
main = print dumbSum

dumbSum :: Int
dumbSum = go 0 0 1
  where
    go :: Int -> Int -> Int -> Int
    go sm ct n
        | ct >= 15000000 = sm
        | n .&. 1 == 0   = go (sm + n) (ct+1) (n+1)
        | otherwise      = go sm ct (n+1)

您将获得C和预期的Haskell版本之间的运行时间的近似关系。
这种算法并不是GHC所教的如何优化的好方法，在将有限的人力投入到这些优化中之前，还有其他更大的鱼可以进行油炸。

关于haskell - 对大量数字求和太慢，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13399032/