haskell - 对大量数字求和太慢了

Question

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

哈斯克尔：

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)，需要作为一个函数来实现。

score 24 · Accepted Answer

列表不是循环

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

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 的融合所需要的。剩下的是 boxingInt和构建列表单元格。如果你给它一个循环，就像你把它给 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 被教导要优化的，在有限的人力投入到这些优化之前，其他地方还有更大的鱼可炒。

score 11 · Accepted Answer

列表融合在这里不起作用的问题实际上是相当微妙的。假设我们定义了RULE融合列表的权利：

import GHC.Base
sum2 :: Num a => [a] -> a
sum2 = sum
{-# NOINLINE [1] sum2 #-}
{-# RULES "sum" forall (f :: forall b. (a->b->b)->b->b).
                sum2 (build f) = f (+) 0 #-}

（简短的解释是我们定义sum2为的别名sum，我们禁止 GHC 提前内联，因此在被淘汰RULE之前有机会触发sum2。然后我们sum2直接在列表生成器旁边查找build（参见定义）并替换它通过直接算术。）

这取得了喜忧参半的成功，因为它产生了以下核心：

Main.$wgo =
  \ (w_s1T4 :: GHC.Prim.Int#) ->
    case GHC.Prim.remInt# w_s1T4 2 of _ {
      __DEFAULT ->
        case w_s1T4 of wild_Xg {
          __DEFAULT -> Main.$wgo (GHC.Prim.+# wild_Xg 1);
          15000000 -> 0
        };
      0 ->
        case w_s1T4 of wild_Xg {
          __DEFAULT ->
            case Main.$wgo (GHC.Prim.+# wild_Xg 1) of ww_s1T7 { __DEFAULT ->
            GHC.Prim.+# wild_Xg ww_s1T7
            };
          15000000 -> 15000000
        }
    }

这是一个很好的、完全融合的代码——唯一的问题是我们$wgo在非尾调用位置调用。这意味着我们不是在看一个循环，而是实际上在一个深度递归的函数中，具有可预测的程序结果：

Stack space overflow: current size 8388608 bytes.

这里的根本问题是 Prelude 的列表融合只能融合右折叠，而将和计算为右折叠直接导致过多的堆栈消耗。显而易见的解决方法是使用一个真正可以处理左折叠的融合框架，例如 Duncan 的流融合包，它实际上实现了sum融合。

另一种解决方案是绕过它 - 并使用右折叠实现左折叠：

main = print $ foldr (\x c -> c . (+x)) id [2,4..15000000] 0

这实际上使用当前版本的 GHC 生成接近完美的代码。另一方面，这通常不是一个好主意，因为它依赖于 GHC 足够智能以消除部分应用的功能。已经将 a 添加filter到链中将破坏该特定优化。

score 5 · Accepted Answer

对前 15,000,000 个偶数求和：

{-# LANGUAGE BangPatterns #-}

g :: Integer    -- 15000000*15000001 = 225000015000000
g = go 1 0 0
  where
    go i !a c  | c == 15000000 = a       
    go i !a c  | even i = go (i+1) (a+i) (c+1)
    go i !a c           = go (i+1) a c

应该是最快的。

score 4 · Accepted Answer

如果您想确保只遍历列表一次，您可以显式编写遍历：

nats = [1..] :: [Int]

requiredOfX :: Int -> Bool -- this way you can write a different requirement
requiredOfX x = even x

dumbSum :: Int
dumbSum = dumbSum' 0 0 nats
  where dumbSum' acc 15000000 _ = acc
        dumbSum' acc count (x:xs)
          | requiredOfX x = dumbSum' (acc + x) (count + 1) xs
          | otherwise     = dumbSum' acc (count + 1) xs

score 3 · Accepted Answer

首先，您可以像年轻的高斯一样聪明，并计算O(1)中的总和。

除了有趣的东西，您的 Haskell 解决方案使用列表。我很确定您的 C/C++ 解决方案不会。（Haskell 列表非常易于使用，因此即使在可能不合适的情况下也很想使用它们。）尝试对此进行基准测试：

sumBy2 :: Integer -> Integer
sumBy2 = f 0
  where
    f result n | n <= 1     = result
               | otherwise  = f (n + result) (n - 2)

-O2使用带参数的GHC 编译它。该函数是尾递归的，因此编译器可以非常有效地实现它。

更新：如果你想使用even函数，它是可能的：

sumBy2 :: Integer -> Integer
sumBy2 = f 0
  where
    f result n | n <= 0     = result
               | even n     = f (n + result) (n - 1)
               | otherwise  = f result (n - 1)

您还可以轻松地将过滤函数设为参数：

sumFilter :: (Integral a) => (a -> Bool) -> a -> a
sumFilter filtfn = f 0
  where
    f result n | n <= 0     = result
               | filtfn n   = f (n + result) (n - 1)
               | otherwise  = f result (n - 1)

score 2 · Accepted Answer

2

严格的版本工作得更快：

foldl' (+) 0 $ take 15000000 [2, 4..]

于 2012-11-15T14:09:05.063 回答

score 1 · Accepted Answer

另一件需要注意的是，这nats就是evens所谓的常量应用形式，简称 CAF。基本上，这些对应于没有任何参数的顶级定义。CAF 有点奇怪，例如是 Dreaded Monomorphism Restriction 的原因；我不确定语言定义是否允许内联 CAF。

在我关于 Haskell 执行方式的心智模型中，当dumbSum返回一个值时，evens将被评估为类似于2:4: ... : 30000000 : <thunk>和natsto 1:2: ... : 30000000 : <thunk>，其中<thunk>s 表示尚未查看的内容。如果我的理解是正确的，那么这些分配:确实必须发生并且不能被优化掉。

因此，在不过多更改代码的情况下加快速度的一种方法是简单地编写：

dumbSum :: Int
dumbSum = sum . take 15000000 . filter even $ [1..]

或者

dumbSum = sum $ take 15000000 evens where
    nats = [1..]
    evens = filter even nats

在我用编译的机器上，-O2仅此一项似乎就可以提高大约 30% 的速度。

我不是 GHC 鉴赏家（我什至从来没有介绍过 Haskell 程序！），所以我可能会大失所望。

haskell - 对大量数字求和太慢了

7 回答 7

列表不是循环

Related

Reference