Haskell Fibonacci似乎很慢

Question

我正在学习Haskell,我写了一个简单的Fibonacci函数:

fib :: Int -> Int

fib 1 = 1
fib 0 = 0
fib n = (fib (n-1)) + (fib (n-2))

它似乎编译好了,并将此脚本加载到GHCI REPL我可能会乱用一些数字.我试过了

fib 33

并且惊讶地发现结果需要大约4秒钟.(对不起,我不知道如何计算Haskell中的函数,所以自己算一算).

Fib 33并不特别重要.答案不到400万.所以我假设我的代码是不是写得很好,还是有一些问题与我也许做递归的方式(当然,它写得不好的,因为它没有考虑到负整数).问题是,为什么它变慢？任何帮助赞赏.

Answer 1

评估花费的时间比您预期的要长,因为您的功能不使用memoization.有关如何使用memoization在Haskell中定义fibonacci函数的答案,请参阅此问题或该问题.

Answer 2

你把时间与其他语言比较了吗？

这是具有O(2 ^ n)复杂度的递归算法.在n = 33时,会给出惊人的呼叫量.如果算上每次这样的呼叫有多少毫秒或几纳秒,你就会得到一个关于实际性能的非常显着的答案.

请记住,一些编译器/执行环境可能会缓存函数返回值(Frerich有更好的内存来调用它:memoization),这可以大大提高此算法的性能.在这种情况下它不会发生,因此所有这些2 ^ n递归调用都会发生.