Haskell:为什么我的斐波那契数列实现效率低下？

Question

作为学习 Haskell 的一部分，我编写了以下斐波那契游戏程序:

fibonacci 0 = [0]       
fibonacci 1 = [0,1]          
fibonacci n = let   
                foo'1 = last (fibonacci (n-1))
                foo'2 = last (fibonacci (n-2))
              in  reverse((foo'1 + foo'2):reverse (fibonacci (n-1)))

该程序有效:

ghci>fibonacci 6
[0,1,1,2,3,5,8]

但是，性能随着 n 呈指数下降。如果我给它一个 30 的参数，它大约需要一分钟才能运行，而不是在 6 时立即运行。看起来懒惰的执行让我很恼火，斐波那契对最终列表中的每个元素都运行一次。

我是在做一些愚蠢的事情还是错过了什么？

(我已经摆脱了可能这样做的++ 想法)

Answer 1

正如评论中所指出的，您的方法有点过于复杂。特别是，您不需要使用递归调用，甚至不需要使用 reverse 函数来生成斐波那契数列。

线性时间实现

除了 your own answer ，这是一本教科书的单行话，它使用内存法:

fibs :: [Integer]
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

一旦有了 fib，编写 fib 函数就很简单了:

fib :: Int -> [Integer]
fib n
    | n < 0     = error "fib: negative argument"
    | otherwise = take (n+1) fibs

fib 的这种实现的复杂度为 θ(n)，显然比 θ(exp(n)) 好得多。

在 GHCi 中测试

λ> :set +s
λ> fib 6
[0,1,1,2,3,5,8]
(0.02 secs, 7282592 bytes)
λ> fib 30
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040]
(0.01 secs, 1035344 bytes)

如您所见，在我的计算机上，fib 30 的计算时间不到一分钟。

进一步阅读

要更全面地了解如何在 Haskell 中生成斐波那契数列，我建议您引用此 haskell.org wiki