为什么斐波那契的实现速度极快？

Question

斐波那契的这种实现很容易理解，但速度很慢：

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

斐波那契的实现很难理解，但速度非常快。它在我的笔记本电脑上立即计算出第100,000个斐波那契数。

fib = fastFib 1 1

fastFib _ _ 0 = 0
fastFib _ _ 1 = 1
fastFib _ _ 2 = 1
fastFib a b 3 = a + b
fastFib a b c = fastFib (a + b) a (c - 1)

关于后一种实现，这里发生了什么魔力，它是如何工作的？

Answer 1

我只想说明尾递归和第二个程序的速度无关。下面，我重写了你的第一个程序来使用一个适当的尾调用，并且我们比较了第二个程序的执行时间。我也重写了这个，因为它可以简化很多-

fib1 n = slow n id
  where
    slow 0 k = k 0
    slow 1 k = k 1
    slow n k = slow (n - 1) (\a ->
               slow (n - 2) (\b ->
               k (a + b)))

fib2 n = fast n 0 1
  where
    fast 0 a _ = a
    fast n a b = fast (n - 1) b (a + b)

对n=10等微小数字的影响可以忽略不计-

fib1 10
-- 55
-- (0.01 secs, 138,264 bytes)

fib2 10
-- 55
-- (0.01 secs, 71,440 bytes)

但是，即使在n=20附近，我们也注意到fib1-

fib1 20
-- 6765
-- (0.70 secs, 8,787,320 bytes)

fib2 20
-- 6765
-- (0.01 secs, 76,192 bytes)

在< code>n = 30时，这种影响是可笑的。两个程序仍然得到相同的结果，这很好，但是< code>fib1需要30多秒。< code>fib2仍然只需要几分之一秒-

fib1 30
-- 832040
-- (32.91 secs, 1,072,371,488 bytes) LOL so bad

fib2 30
-- 832040 (0.09 secs, 80,944 bytes)

这是因为第一个程序，fib1，进行了两次递归调用。当＜code＞n＜/code＞增长时，此函数的过程使用指数时间和空间。当n=30时，慢速程序将进行1073741824（2³⁰）递归调用。快速程序将仅重复30次。

当n=1000时，我们遇到了fib1。基于fib1 30的性能，我们估计需要1.041082353242204e286，才能完成2个¹⁰⁰⁰递归调用。同时，fib21000轻松地处理了1000个递归-

fib2 1000
-- 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
-- (0.13 secs, 661,016 bytes)

使用添加的k参数可能很难遵循第一个程序的原始重写。使用＜code＞Cont＜/code＞可以让我们看到Haskell熟悉的＜code＞do＜/code＞符号中清晰的步骤序列-

import Control.Monad.Cont

fib1 n = runCont (slow n) id
  where
    slow 0 = return 0
    slow 1 = return 1
    slow n = do
      a <- slow (n - 1)
      b <- slow (n - 2)
      return (a + b)

Answer 2

神奇的是递归公式描述的计算过程的反射、具体化、解释：

fib 0 = 0    -- NB!
fib 1 = 1
fib n = fib (n-1) + fib (n-2)
      --  n1          n2
      = let {n1 = fib (n-1) ; n2 = fib (n-2)} 
        in n1 + n2
      = let {n1 = fib (n-2) + fib (n-3) ; n2 = fib (n-2)} 
      --            n2          n3
        in n1 + n2
      = let {n1 = n2+n3 ; n2 = fib (n-2) ; n3 = fib (n-3)} 
        in n1 + n2
      = let {n1 = n2+n3 ; n2 = fib (n-3) + fib (n-4) ; n3 = fib (n-3)} 
      --                         n3          n4
        in n1 + n2
      = let {n1 = n2+n3 ; n2 = n3+n4 ; n3 = fib (n-3) ; n4 = fib (n-4)} 
        in n1 + n2
      = let {n1 = n2+n3 ; n2 = n3+n4 ; n3 = n4+n5 ; n4 = fib (n-4) ; n5 = fib (n-5)} 
        in n1 + n2
      = .......

，将其查看到最终案例，然后翻转时间箭头（或者只是从右向左读取它），并显式编码let内隐含发生的事情，作为递归模拟的“调用堆栈”操作的一部分。

最重要的是，用 equals 替换 equals，也就是参照透明性 -- 使用 n2 代替 fib （n-2） 的每次出现，等等。

Answer 3

好吧，它很慢，因为每次调用fib可能会导致最多两次（平均更像1.6）调用fib，因此要计算fib 5您调用fib 4和fib 3分别调用fib 3和fib 2，以及fib 2和fib 1，因此我们可以看到每次调用fib（n 1）导致的工作量是调用fib n的两倍。

我们可能观察到的一件事是，我们很多次都在做同样的事情，例如，上面我们做了两次< code>fib 3。如果您必须计算两次，例如< code>fib 100，这可能需要很长时间。

我认为最好从这个开始，而不是试图直接跳入fastFib。如果我要求你手动计算第十个斐波那契数列，我希望你不会通过应用该算法来计算第三个斐波那契数十次。你可能会记得到目前为止你有什么。事实上，人们可以在Haskell中做到这一点。只需编写一个程序来生成斐波那契数列列表（懒惰地）并索引到其中：

mediumFib = (\n -> seq !! n) where
  seq = 0:1:[mediumFib (i-1) + mediumFib (i-2)| i <- [2..]]

这要快得多，但很糟糕，因为它需要大量内存来存储斐波那契数列表，而查找列表的第n个元素很慢，因为必须遵循大量指针。

从头开始计算单个斐波那契数（即尚未计算）需要二次时间。

另一种手工计算第十个斐波那契数的方法是，写下斐波那奇序列，直到得到第十个元素。然后，你再也不需要回顾遥远的过去，也不需要记住你以前计算过的所有事情，你只需要看看前面的两个元素。我们可以想象一个命令式算法来实现这一点

fib(n):
  if (n<2) return n
  preprevious = 0
  previous = 1
  i = 2
  while true:
    current = preprevious + previous
    if (i = n) return current
    preprevious, previous = previous, current

这只是逐步通过递归关系：

f_n = f_(n-2) + f_(n-1)

事实上，我们也可以用Haskell来写：

fastFib n | n < 2     = n
          | otherwise = go 0 1 2 where
  go pp p i | i = n     = pp + p
            | otherwise = go p (pp + p) (i + 1)

这已经很快了，我们也可以把它转换成你有的函数。以下是步骤:

1. 交换pp（前一个）和p（前一个）
的参数顺序
2. 不是向上计数i，而是从n开始并倒数。
3. 将go提取到顶级函数中，因为它不再依赖于n。

这个算法每一步只需要做一次求和，所以是线性时间，速度非常快。计算fib（n1）只是一个小常数，比计算fib（n，要多做的工作。将其与上面的相比，前者的工作量约为前者的1.6倍。

当然有。事实证明有一种巧妙的方法来表达斐波那契数列。我们考虑转换a， b-

T_pq : a -> bq + aq + ap
       b -> bp + aq

具体来说，这是一种特殊情况，其中< code>p = 0和< code>q = 1。我们现在可以做一些代数运算，看看是否有一种简单的方法来表示应用< code>T_pq两次:

T_pq T_pq :
  a -> (bp + aq)q + (bq + aq + ap)(q + p)
  b -> (bp + aq)p + (bq + aq + ap)q
=
  a -> (b + a)(q^2 + 2pq) + a(q^2 + p^2)
  b -> b(q^2 + p^2) + a(q^2 + 2pq)
= T_(q^2 + p^2),(q^2 + 2pq)

现在让我们编写一个简单的函数来计算T_pq^n（a， b）和fib n

tPow p q a b n | n = 1 = (b*q + a*q + a*p, b*p + a*q)
               | otherwise = let (a', b') = tPow p q a b 1 in tPow p q a' b' (n-1)

fib 0 = 0
fib 1 = 1
fib n = fst $ tPow 0 1 1 0 (n-1)

现在我们可以使用我们的关系使tPow更快：

tPow p q a b n | n = 1 = (b*q + a*q + a*p, b*p + a*q)
               | odd n = let (a', b') = tPow p q a b 1 in tPow p q a' b' (n-1)
               | even n = tPow (q*q + p*p) (q*q + 2*p*q) a b (n `div` 2)

为什么这个更快？它更快是因为计算fib（2*n）只是比计算fib n多工作的一个小常量，而在它之前是两倍的工作量，在此之前是四倍的工作量，在此之前是工作量的平方。事实上，步数类似于二进制中n的位数加上n的二进制表示中1s的数量。计算fib 1024只需要大约10步，而以前的算法需要大约1000步。计算十亿个斐波那契数只需要30步，比十亿少得多。