8

任务:“对前 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),需要作为一个函数来实现。

4

7 回答 7

24

列表不是循环

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

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 被教导要优化的,在有限的人力投入到这些优化之前,其他地方还有更大的鱼可炒。

于 2012-11-15T14:34:31.163 回答
11

列表融合在这里不起作用的问题实际上是相当微妙的。假设我们定义了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到链中将破坏该特定优化。

于 2012-11-15T18:03:32.357 回答
5

对前 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

应该是最快的。

于 2012-11-15T14:28:40.610 回答
4

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

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
于 2012-11-15T14:31:04.807 回答
3

首先,您可以像年轻的高斯一样聪明,并计算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)
于 2012-11-15T14:32:31.583 回答
2

严格的版本工作得更快:

foldl' (+) 0 $ take 15000000 [2, 4..]
于 2012-11-15T14:09:05.063 回答
1

另一件需要注意的是,这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 程序!),所以我可能会大失所望。

于 2012-11-15T20:54:11.317 回答