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，但我认为这不会有所作为。

score 19 · Accepted Answer

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

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

score 0 · Accepted Answer

这是我在 haskell 示例中看到最多的 fib 实现：

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

试试它与 python 代码，它可能会快得多。这不是直接翻译，但可能更惯用。

这不是一个直接的答案，但也许没有人希望有一个优化的 fib 会使用你在那里使用的幼稚实现。因此，这不是比较 python 和 haskell 性能的最佳方法。

2 回答 2