Haskell斐波那契数列似乎很慢

Question

我正在学习Haskell，并编写了一个简单的斐波那契函数：

fib :: Int -> Int

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

看起来编译没问题，将这个脚本加载到GHCI REPL中，我可以尝试一些数字操作。 我试过了。

fib 33

我曾经试着用Haskell编写Fibonacci数列并测试了一下，结果发现计算结果需要约4秒钟的时间（很抱歉我还不知道如何在Haskell中计时函数，所以我自己计数了）。

Fibonacci数列的第33项并不是特别复杂，答案小于400万。因此，我认为我的代码可能写得不太好，或者可能存在递归方式的问题（实际上，我的代码没有考虑到负整数）。问题在于，为什么它运行得这么慢呢？任何帮助都将不胜感激。

- user485498

---

这个问题似乎适合在 CodeReview 上进行。 - Alexander

当查看您的代码时，想象一下例如fib(5)被计算的频率。每次迭代，您都会重新计算所有“内部”的斐波那契数。 - WeSt

你应该使用经典的惰性无限列表版本：fibs = 0 : 1 : zipWith (+) fibs (tail fibs)，其中 fib n = fibs!!n。请参阅关于斐波那契数列的 Haskell Wiki。有趣的是，斐波那契因这个序列而闻名，但实际上这只是他所著书籍中介绍西欧位值的一个小练习。 - AndrewC

Answer 1

评估所花费的时间比您预期的时间长，这是因为您的函数没有使用备忘录技术。有关如何使用备忘录在Haskell中定义斐波那契函数的答案，请参见例如此问题或那个问题。

- Frerich Raabe

---

记忆化链接非常清楚地解释了这个问题。 - user485498

根据你所使用的教材，你可能会发现HaskellWiki链接显示了“教科书方法”（在“递归记忆化”部分）。 - Frerich Raabe

在通往高阶启示的路上，我不知道怎么会错过 fib=0:1:zipWith (+) fib (tail fib)。这是一个关于“一切”的教科书式例子。我可以闭着眼睛在手机上打出它（我刚刚就是这样做的）。 - n. m.

这个回答在如此短的时间内获得如此之多的赞成票，确实让我感到不解。它非常接近于仅包含链接的答案... - jub0bs

它不是那种类型。它的使用方式类似于这样。我不确定它是否适合作为一个答案。 - n. m.

Answer 2

你有没有将这个时间与其他语言进行比较？

这是一个具有O(2^n)复杂度的递归算法。当n=33时，调用的次数惊人。如果您计算每个这样的调用所需的毫秒或纳秒数量，则会得出一个非常显著的答案，以了解实际性能。

请记住，某些编译器/执行环境可能会缓存函数返回值（Frerich更好地记得如何称之为备忘录），这极大地提高了此算法的性能。在这种情况下，它并没有发生，因此所有这些2^n次递归调用都确实发生了。

- Gerino

---

从技术上讲，其复杂度为O(fib n)，因此大约为O(1.68^n)，略优于O(2^n)。尽管如此，这并不影响您的观点：它的复杂度仍然是指数级的，因此递归调用的数量很快变得不切实际。 - chi

Answer 3

你的算法不是很好。你可以使用记忆化进行一些改进，使其复杂度达到O(n)。通过使用分治法，你可以将其提高至O(log n)：

import Data.Matrix

fib :: Integer -> Integer
fib n = ((fromLists [[1,1],[1,0]]) ^ n) ! (1,2)

思想是乘法是可结合的，所以您可以在适当的位置放上括号：

5^10 = (5 * 5 * 5 * 5 * 5) * (5 * 5 * 5 * 5 * 5) = (5 * 5 * 5 * 5 * 5) ^ 2 = ( (5 * 5) * (5 * 5) * 5) ^ 2 = ( (5 * 5 ) ^ 2 * 5) ^ 2 = (((5 ^ 2) ^ 2) * 5) ^2

矩阵乘法也可以应用相同的模式。Haskell已经在其默认库中实现了此操作符（^）。

确实有效：

map fib [1..21]
--! [1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946]

- stefan.schwetschke

Answer 4

这里是一个优化版本，带有一个辅助函数。虽然比上面给出的懒惰无限列表还要慢，但对像我这样的新手来说更加直观易懂！

fib :: Integer -> Integer
fib 0 = 0
fib 1 = 1
fib n = fib' 0 1 2 n

fib' :: Integer -> Integer -> Integer -> Integer -> Integer
fib' a b i n = if i > n then b else fib' b (a + b) (i + 1) n

注：仅适用于正数

- amankkg