将斐波那契数列计算为不动点的复杂性

Question

我已经意识到下面的程序

fibMap :: [Integer] -> [Integer]                                                          
fibMap xs = 1 : 1 : (zipWith (+) xs $ tail xs)                                            
                                                                                          
fix :: (b -> b) -> b                                                                      
fix f = f $ fix f 

> take 100 $ fix fibMap

出奇的快。它比递归定义快得多：

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

> fib 100

我很难理解定点定义实际上归结为哪种程序算法。它之所以快，是因为 Haskell 的编译器做了一些巧妙的优化，还是它本质上很快？

让我们稍微解开固定点：

x = fix fibMap = fibMap $ fix fibMap 
= 1:1:(zipWith (+) y $ tail y) 
   where y = fix fibMap = fibMap $ fix fibMap

Haskell 编译器是否识别 x = y 和“短路”？它会更多地了解列表 x，还是会从头开始重新计算 y 的所有内容？

我觉得短融合会产生快速算法，而重新计算 y 会给出大致等同于递归算法的结果？

是否有任何 tricks/ways 想法可以更轻松地确定使用定点的算法的复杂性？它对编译器的评估策略敏感吗？

Answer 1

关键思想是共享工作。在原始版本中，fib (n-2) 从头开始计算两次 (fib n = fib (n-1) + fib (n-2) = fib (n-2) + fib (n-2) + fib (n-3))。在列表版本中，参数xs表示递归调用，计算一次，使用两次。

fix fibMap = fibMap (fix fibMap)
           = let xs = fix fibMap in
             1 : 1 : zipWith (+) xs (tail xs)

思考这项工作的一种方法是将目标从“如何计算第 n 个斐波那契数”更改为“如何计算 前 n 个斐波那契数的列表”。对于 n > 2:

前两个斐波那契数是1和1；
剩余的 (n-2) 个可以从 第一个 (n-1) 个斐波那契数 中计算出来，方法是将该列表与自身压缩。

它仍然是一个递归算法，但是只有一个递归调用，这是避免指数爆炸的方法。

事实上，根据上面的定义，您可以通过等式推理正式证明 take n (fix fibMap)（n > 2）的以下恒等式：

take n (fix fibMap)
  = let ys = take (n-1) (fix fibMap) in
    1 : 1 : zipWith (+) ys (tail ys)

上述算法进行了大约n次递归调用，每次调用它压缩一个长度至多为n的列表，因此复杂度至多为二次(O(n^2))，这实际上是一个紧密结合。

您可能期望线性复杂度界限 (O(n))，但为此您必须稍微调整算法。问题当然是每一步的“压缩”操作都做了很多多余的工作。

这就是fix这两个定义的区别：

fix f = f (fix f)

和

fix f = let self = f self in self

它们在产生相同值的意义上是等价的，但它们在操作上有所不同：在某些情况下，第二个执行效率更高（例如这个）。

在第一个定义中，当 f 需要它的参数时，它会从头开始重新计算 fix f。

在第二个定义中，f的参数是它自己的结果，所以当f需要它的参数时，它将使用它已经部分计算的结果。

现在在定义斐波那契数列的具体情况下，使用上面第一个版本 fix 的定义效率低下，因为它对 fibMap 进行了无限多次调用（因此 zipWith):

fix fibMap = fibMap (fix fibMap) = fibMap (fibMap (fix fibMap)) = ...

而第二个版本只使用了一次 fibMap：

fiblist = let self = fibMap self in self

-- equivalent definition
fiblist = fibMap fiblist

将斐波那契数列计算为不动点的复杂性

Complexity of computing Fibonacci sequence as a fixpoint

haskell

fixpoint-combinators