为什么这个Fibonacci在Python中比Haskell快得多

Question

我有一个算法可以用来计算第n个斐波那契数，在Python中的写法是：

def fib(n):
    if n == 0:
        return 1
    if n == 1:
        return 1
    else:
        return fib(n-1) + fib(n-2)

而在Haskell中的写法是：

fib :: Integer -> Integer
fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

我本以为Haskell的计算速度会更快，或者差不多一样快，但如果用的数字超过40，比如n=40，Python的代码运行速度快很多，大约快了三倍。我使用的是GHCi和Ipython，但我觉得这不应该影响结果。

Answer 1

这是我在 Haskell 示例中看到的最常见的斐波那契数列实现：

fib n = fibs!!n
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

试试这个和 Python 代码的速度对比，可能会快很多。虽然这不是直接的翻译，但可能更符合 Haskell 的写法。

这不是一个直接的回答，但也许没有人会用你那种简单的实现来优化斐波那契数列。因此，这样比较 Python 和 Haskell 的性能并不是最好的方法。

更多内容可以查看 Haskell 中的斐波那契数列

Answer 2

你提到你在GHCI中运行了Haskell代码，这就意味着你是在没有优化的情况下运行的。这意味着没有进行严格性分析，所以整个过程都是懒惰地计算，这样就产生了很多不必要的“懒惰计算块”。这就能解释为什么运行得比较慢。

另外，正如delnan在评论中提到的，ghci的速度远远慢于用ghc编译代码后再运行，即使没有优化。当我在我的电脑上测试你的代码时，编译后没有优化的运行时间是有优化时的两倍，但仍然比运行Python代码的时间要短。而在ghci中运行则要花费更长的时间。