为什么Haskell中递归列表如此缓慢？

Question

我对Haskell还很陌生，我在Haskell中定义了一个函数：

febs :: (Integral a)=> a -> a
febs n 
    | n<=0 =0
    | n==1 =1
    | n==2 =1
    | otherwise =febs(n-1)+febs(n-2)

但是，它运行得非常缓慢，当我输入“febs 30”时，需要大约10秒钟的时间， 而在C++中执行相同的函数时，速度非常快。

int febs(int n)
{
    if(n == 1 || n ==2)
    {
        return 1;
    }
    return febs(n-1)+febs(n-2);
}

有没有办法提高我的Haskell函数的执行速度？

- aasa

---

这个函数传统上被称为"fib"或"fibs"，因为它可以给你斐波那契数。只是想先把我的学究气息表现出来 :P。 - Tikhon Jelvis

Answer 1

以下是一个奇怪的比较，原因如下：

1. 你没有说明你是否使用了什么选项编译Haskell代码。如果你只是在ghci中运行它，那么当然会很慢——你正在将解释性代码与编译后的代码进行比较。

2. 你的Haskell代码是多态的，而你的C++代码是单态的（也就是说，你使用了一个类型类 Integral a => a -> a 而不是具体类型的 Int -> Int）。因此你的Haskell代码比你的C++代码更加通用，因为它可以处理任意大的整数，而不仅仅局限于 Int 类型的范围内。虽然编译器有可能会对这个进行优化，但我不能确定。

如果我把以下代码放在 fib.hs 文件中：

fibs :: Int -> Int
fibs n = if n < 3 then 1 else fibs (n-1) + fibs (n-2)

main = print (fibs 30)

并使用 ghc -O2 fib.hs 进行编译，然后它的运行速度足够快，以至于对我来说看起来是瞬间完成的。你应该尝试一下，并看看它与 C++ 代码相比如何。

- Chris Taylor

---

其实，我不确定。我想你得看看核心，但我经验不足，做不到这一点！ - Chris Taylor

实际上，我可以运行两个版本（带有两个签名），并比较运行时间。而当我说“我”时，我真的是指“你”，因为我必须启动Linux :P。 - Tikhon Jelvis

它发挥了作用。由于它是递归的，所以无法内联。在使用优化编译（始终假定为GHC）时，如果它在与定义它的源文件中单态地使用，则会得到一个特殊化。如果没有类型签名，在main中使用它将是Integer，因此比使用Int要慢一些。如果您在不同的文件中定义它并在其中使用，除非您将其设置为 {-# INLINABLE #-}，否则会得到非常慢的多态代码。 - Daniel Fischer

谢谢，我尝试使用Int，它会更快。我也尝试使用Python shell来完成这项工作，它比GHCi中的要快一点。 - aasa

@aasa，请确保你使用的是 -O2 而不是 -o2。另外，那些询问内联的人，我相当确定 GHC 不会内联定义，因为它是一个递归函数。但我可能错了；检查一下 Core！ - Axman6

Answer 2

尝试使用优化编译。使用 GHC 7.4.1 和 -O2，你的程序运行非常迅速：

$ time ./test 
832040

real    0m0.057s
user    0m0.056s
sys     0m0.000s

这是使用 main = print (febs 30) 的代码。

---

关于 Chris Taylor 答案中的多态性考虑，这里是使用 OP 的多态斐波那契函数计算 febs 40：

$ time ./test 
102334155

real    0m5.670s
user    0m5.652s
sys     0m0.004s

这里有一个非多态的版本，即将 OP 的签名替换为 Int -> Int:

$ time ./test 
102334155

real    0m0.820s
user    0m0.816s
sys     0m0.000s

根据Tikhon Jelvis的评论，有趣的是看看加速是否由于将Integer替换为Int，还是由于消除了多态性。这里是相同的程序，除了根据Daniel Fischer的评论，将febs移动到一个新文件中，并且具有febs :: Integer -> Integer：

$ time ./test 
102334155

real    0m5.648s
user    0m5.624s
sys     0m0.008s

再次使用不同文件中的febs，并且具有与最初相同的多态签名：

$ time ./test 
102334155

real    0m16.610s
user    0m16.469s
sys     0m0.104s

- gspr

---

“Integral”类型默认为“Integer”。我很好奇性能上的变化是仅仅因为“Integer”与“Int”的区别，还是多态性也有影响。 - Tikhon Jelvis

你把函数定义在和 main 同一个文件里了，对吗？如果是分开放在不同的文件中，并使用多态代码，febs 40 时的运行时间为 15.5 秒，Integer -> Integer 时为 5.4 秒，Int -> Int 时为 0.86 秒。@TikhonJelvis 这就是你的问题的答案。而使用 gcc -O3 的话只需要 0.3 秒。 - Daniel Fischer

你必须在定义函数的地方告诉 GHC 函数应该被专门化为某些类型({-# SPECIALISE foo :: Int -> Int, Word -> Integer #-} [也可接受美式拼写])，或者 - 如果需要 GHC >= 7 [可能是 7.2，不确定] - 使用 {-# INLINABLE foo #-} 指令表明它应该在接口文件中公开以进行内联/优化/专门化。然后（始终使用 -O2），它将自动完成，至少如果嵌套不太深的话[我可以想象如果您的调用树有1000个多态函数，则优化器会放弃]。 - Daniel Fischer

@DanielFischer：谢谢！我相信你的这条评论一定为我节省了不少时间。我之前听说过INLINABLE，但一直以为它只是关于内联的问题。如果有了INLINABLE，那么SPECIALIZE是否就变得多余了呢？ - gspr

一般来说是这样的。使用INLINABLE关键字，会在使用处生成一个专门的版本。如果您在许多模块中使用多态函数的一个特定类型，则每个模块都会得到自己的专门版本，此时使用SPECIALISE编译指示符可以减少代码大小。 - Daniel Fischer

Answer 3

您也可以这样编写函数：

fibs = 0:1:zipWith (+) fibs (tail fibs)

这是非常快的，即使对于大规模的'n'也可以立即执行：

Prelude> take 1000 fibs 

- applicative_functor

---

是的，但这在渐近意义下是不同的。我认为真正的问题是比较C++和Haskell，因此使用不同的算法是不可行的。不过这通常是一个好建议。 - Tikhon Jelvis

或者，更酷的是这样：fibs = 0 : scanl (+) 1 fibs - Ed'ka

非常感谢，这是一个很棒的解决方案，我可以从这些代码中感受到 Haskell 的强大。 - aasa

@Ed'ka 为什么要半途而废？fix ((0:) . scanl (+) 1)。 - Daniel Fischer

@DanielFischer 这取决于使用哪个 fix，fix f = f (fix f) 还是 fix f = let x = f x in x。如果使用第一个，我们将会有一个不太愉快的惊喜。当然，Data.Function 使用的是第二个。 :) - Will Ness