为什么这个Fibonacci在Python中的评估要比Haskell快得多

Question

我有一个计算第n个Fibonacci数的算法,在Python中它表示为:

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

在哈斯克尔:

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编译代码然后运行它要慢得多 - 即使没有优化也是如此.当我在我的PC上测试你的代码时,在没有优化的情况下编译后运行所需的时间是优化的两倍,但是运行Python代码的时间仍然少.在ghci中运行需要比这更长的时间.