python - 为什么这个斐波那契在 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 的计算速度会更快或大约在同一时间，但如果使用高于 n=40 的数字，python 代码的计算速度会快很多 (~x3)。我正在使用 GHCi 和 Ipython，但我认为这不会有什么不同。

Answer 1

你说你在 GHCI 中运行了 Haskell 代码，这意味着你在没有优化的情况下运行它。这意味着没有进行严格性分析，所以整个事情都是懒惰地评估的，产生了很多不必要的 thunk。这可以解释为什么它变慢了。

此外，正如 delnan 在评论中指出的那样，ghci 比使用 ghc 编译代码然后运行它要慢得多——即使没有优化。当我在我的电脑上测试你的代码时，在没有优化的情况下编译后运行花费的时间是优化的两倍，但仍然比运行 Python 代码的时间少。在 ghci 中运行需要的时间比这长得多。