程序设计中的计算复用(Computational Reuse)

从斐波那契数列说起

我想几乎每一个程序员对斐波那契（Fibonacci）数列都不会陌生，在很多教科书或文章中涉及到递归或计算复杂性的地方都会将计算斐波那契数列的程序作为经典示例。如果现在让你以最快的速度用C#写出一个计算斐波那契数列第n个数的函数（不考虑参数小于1或结果溢出等异常情况），我不知你的程序是否会和下列代码类似：

public static ulong Fib(ulong n)
{
    return (n == 1 || n == 2) ? 1 : Fib(n - 1) + Fib(n - 2);
}

这段代码应该算是短小精悍（执行代码只有一行），直观清晰，而且非常符合许多程序员的代码美学，许多人在面试时写出这样的代码可能心里还会暗爽。但是如果用这段代码试试计算Fib(100)我想就再也爽不起来了，估计下星期甚至下个月前结果很难算得出来。

看来好看的代码未必中用，如果程序在效率不能接受那美观神马的就都是浮云了。如果简单分析一下程序的执行流，就会发现问题在哪，以计算Fibonacci(5)为例：




从上图可以看出，在计算Fib(5)的过程中，Fib(1)计算了两次、Fib(2)计算了3次，Fib(3)计算了两次，本来只需要5次计算就可以完成的任务却计算了9次。这个问题随着规模的增加会愈发凸显，以至于Fib(100)已经无法再可接受的时间内算出。虽然可以通过尾递归优化将双递归变为单递归，但是效果也并不理想。

这是一个非常典型的忽视“计算复用”的例子。计算复用的目标在于保证计算过程中同一计算子过程只进行一次，通过保存子过程计算结果并复用来提高计算效率。其实类似上面的代码出现在很多教科书中，如果是为了展示斐波那契数列的数学特性当然无可厚非，但是作为计算机程序就很有问题了。因为数学和计算科学是有区别的，数学要求严谨和简洁的表达，而计算科学则需要尽量快的得出结果，好的数学公式未必是好的计算公式。这也说明程序设计不是简单的将数学语言翻译为计算机语言就可以了，程序员应该能将数学语言首先翻译成计算科学语言（算法？），然后再翻译成机器语言。因此程序员的工作绝不是机械的，而是要有一定的创造性，所以必要的算法知识对程序员至关重要，因为算法教会程序员如何用最有效率的方式去编写程序。

言归正传，根据以上分析，可以写出一个更高效的斐波那契数列计算程序：

public static ulong Fib(ulong n)
{
    if (n == 1 || n == 2)
    {
        return 1;
    }
    ulong m1 = 1, m2 = 1;
    for (ulong i = 3; i <= n; i++)
    {
        m2 = m1 + m2;
        m1 = m2 - m1;
    }

    return m2;
}

这段代码可能看起来不如上一段那么优美，但是其效率却是第一段代码不可比拟的。例如计算Fib(40)，在我的机器上，第一段代码用时3.5秒，而第二段代码小于0.001秒。这个差距随着规模增大会更明显，例如Fib(100)，第一段代码可能需要几天甚至几周，而第二段代码耗时仍然小于0.001秒。天壤之别！

如果从计算复杂性的角度分析，第一段代码的复杂度为O(1.6^n)，对数学敏感的朋友应该能体会到这个函数可怕的增长速度，这甚至不是一个多项式级别的复杂度，而第二段代码仅为O(n)。看到如此简单一个例子出现如此差别，还能说程序员学习算法没有用吗。

上面代码对于“计算复用”的思想体现不是很明显，因为我们仅仅需要一个结果，中间结果都被丢弃了，如果是计算1<=i<=n的所有Fib(i)，那么计算复用的思想就会体现的比较明显。

矩阵乘法与Strassen算法

下面说一个将计算复用发挥到极致的例子，说实话直到现在每次看到Strassen算法我都觉得震撼，不知Strassen当年是长了何等天才的脑子才发现这么漂亮的一个算法。

矩阵计算在许多领域如机器学习、图形图像处理、模式识别中均占有重要地位。而计算两个n*n矩阵乘积的运算是矩阵计算中常见的计算。由矩阵理论可知，普通方法计算两个n阶方阵的乘积需要进行n^3次乘法计算，其计算复杂度自然是O(n^3)。但是德国数学家Volker Strassen通过拆分矩阵并复用计算结果，发现了一种复杂度为O(n^2.81)的算法，这个算法简单说来如下。

假设n为2的幂（不为2的幂也能计算，这里是为了方便说明），A和B是两个n阶方阵，则A和B分别可以分解成4个n/2阶方阵：




则：




可惜这样经过8次n/2阶方阵相乘，复杂度还是O(n^3)，没有降低复杂度。天才的Volker Strassen发现了一种通过计算7次n/2阶方阵来得出n阶方阵乘积的方法。具体来说，假设每个矩阵的积可以写成如下形式：



然后设：



这样通过7次n/2矩阵的相乘计算出P1-P7，然后：



这样就组合出了AB，这个方法的复杂度为O(n^2.81)，这个算法实在是太漂亮了。天才！绝对的天才啊！对于这种人除了无限崇敬我真是没有其它想法了，能将计算复用发挥到如此境地，不知世间能有几人。

计算复用对软件开发的启示

也许有的朋友会说，“我又不开发数值计算型程序，也不会接触如此复杂的算法，计算复用与我何干？”。实际上即使开发非数值型程序，计算复用的思想也是大有用途的。例如我曾经在一个真实的PHP开发的行业系统中见过类似这样的代码：

foreach($items as $k => $v){
    //...
    $money = $v->money + getTax();
    //...
}

当时我问开发这个程序的人这里getTax的返回值和每个item有关系吗，他说税费是一套复杂的算法算出来的，但是其值固定的。那这里可就太浪费了，每次循环都计算一次，如果改为如下：

$tax = getTax();
foreach($items as $k => $v){
    //...
    $money = $v->money + $tax;
    //...
}

则可以节省不少计算资源。在后来的沟通中发现这个问题原来是重构的遗留问题，以前系统中的税率计算是写在程序里的，后来发现这个计算越来越多，就使用“Extract Method”重构模式提取成了getTax函数，但是这样的后果就是到处都是getTax调用，有的程序段甚至调用七八次，但是如果应用计算复用的思想，则应该在脚本开始只计算一次税费并保存，后面全都使用这个变量而不是每次调用getTax。

总之，只要某个计算结果与执行上下文无关，并且在一个执行流中超过一次被使用，则应该使用计算复用。

这个例子还算明显的，有时可能不会这么明显，例如我们知道JavaScript中从深层函数中引用全局对象的代价是很高的，因为需要遍历作用域链（当然是隐式的），因此在JS中如果深层函数代码频繁使用全局对象，则要付出很高的代价。如果程序员不懂得对象及作用域链相关知识，则不会发现这种潜在的效率问题，而正确的做法是使用一个局部变量保存对全局对象的引用而不是每次都直接使用全局变量。

很多成熟的产品也处处体现着计算复用的思想，如在PHP中，下面代码可以得到一个数组的元素个数：

echo count($arr);

如果我们来实现，最自然的想法就是遍历数组。但是PHP的开发者明显更聪明，他们在建立数组时同时建立一个与之关联的内部的数量计数变量（对PHP程序员透明），随着数组元素的增减，这个变量也相应增减，每次调用count函数直接返回这个变量即可，这就将count的复杂度从O(n)降为O(1)，这也是计算复用的一个典型应用。

另外，其实计算复用和缓存的概念是相通的，很多缓存系统就使用了计算复用的思想。

原文：http://www.cnblogs.com/leoo2sk/archive/2011/03/03/computational-reuse.html