從斐波那契數列說起

　　我想幾乎每一個程序員對斐波那契（Fibonacci）數列都不會陌生，在很多教科書或文章中涉及到遞歸或計算復雜性的地方都會將計算斐波那契數列的程序作為經典示例。如果現在讓你以最快的速度用C#寫出一個計算斐波那契數列第n個數的函數（不考慮參數小于1或結果溢出等異常情況），我不知你的程序是否會和下列代碼類似：

　　這段代碼應該算是短小精悍（執行代碼只有一行），直觀清晰，而且非常符合許多程序員的代碼美學，許多人在面試時寫出這樣的代碼可能心里還會暗爽。但是如果用這段代碼試試計算Fib(100)我想就再也爽不起來了，估計下星期甚至下個月前結果很難算得出來。

　　看來好看的代碼未必中用，如果程序在效率不能接受那美觀神馬的就都是浮云了。如果簡單分析一下程序的執行流，就會發現問題在哪，以計算Fibonacci(5)為例：

　　從上圖可以看出，在計算Fib(5)的過程中，Fib(1)計算了兩次、Fib(2)計算了3次，Fib(3)計算了兩次，本來只需要5次計算就可以完成的任務卻計算了9次。這個問題隨著規模的增加會愈發凸顯，以至于Fib(100)已經無法再可接受的時間內算出。雖然可以通過尾遞歸優化將雙遞歸變為單遞歸，但是效果也并不理想。

　　這是一個非常典型的忽視“計算復用”的例子。計算復用的目標在于保證計算過程中同一計算子過程只進行一次，通過保存子過程計算結果并復用來提高計算效率。其實類似上面的代碼出現在很多教科書中，如果是為了展示斐波那契數列的數學特性當然無可厚非，但是作為計算機程序就很有問題了。因為數學和計算科學是有區別的，數學要求嚴謹和簡潔的表達，而計算科學則需要盡量快的得出結果，好的數學公式未必是好的計算公式。這也說明程序設計不是簡單的將數學語言翻譯為計算機語言就可以了，程序員應該能將數學語言首先翻譯成計算科學語言（算法？），然后再翻譯成機器語言。因此程序員的工作絕不是機械的，而是要有一定的創造性，所以必要的算法知識對程序員至關重要，因為算法教會程序員如何用最有效率的方式去編寫程序。

　　言歸正傳，根據以上分析，可以寫出一個更高效的斐波那契數列計算程序：

　　這段代碼可能看起來不如上一段那么優美，但是其效率卻是第一段代碼不可比擬的。例如計算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階方陣乘積的方法。具體來說，設：

　　注意在計算P1-P7過程中，雖然右邊共有20個子矩陣乘積，但是去重復后只有ae，bg，af，bh，ce，dg，cf，dh，只有7個！因此通過計算復用的思想可以通過7次子矩陣乘積結果計算出P1-P7，然后：

　　這樣就組合出了AB，這個方法的復雜度為O(n^2.81)，這個算法實在是太漂亮了。天才！絕對的天才啊！對于這種人除了無限崇敬我真是沒有其它想法了，能將計算復用發揮到如此境地，不知世間能有幾人。

　　計算復用對軟件開發的啟示

　　也許有的朋友會說，“我又不開發數值計算型程序，也不會接觸如此復雜的算法，計算復用與我何干？”。實際上即使開發非數值型程序，計算復用的思想也是大有用途的。例如我曾經在一個真實的PHP開發的行業系統中見過類似這樣的代碼：

　　當時我問開發這個程序的人這里getTax的返回值和每個item有關系嗎，他說稅費是一套復雜的算法算出來的，但是其值固定的。那這里可就太浪費了，每次循環都計算一次，如果改為如下：

　　則可以節省不少計算資源。在后來的溝通中發現這個問題原來是重構的遺留問題，以前系統中的稅率計算是寫在程序里的，后來發現這個計算越來越多，就使用“Extract Method”重構模式提取成了getTax函數，但是這樣的后果就是到處都是getTax調用，有的程序段甚至調用七八次，但是如果應用計算復用的思想，則應該在腳本開始只計算一次稅費并保存，后面全都使用這個變量而不是每次調用getTax。

　　總之，只要某個計算結果與執行上下文無關，并且在一個執行流中超過一次被使用，則應該使用計算復用。

　　這個例子還算明顯的，有時可能不會這么明顯，例如我們知道JavaScript中從深層函數中引用全局對象的代價是很高的，因為需要遍歷作用域鏈（當然是隱式的），因此在JS中如果深層函數代碼頻繁使用全局對象，則要付出很高的代價。如果程序員不懂得對象及作用域鏈相關知識，則不會發現這種潛在的效率問題，而正確的做法是使用一個局部變量保存對全局對象的引用而不是每次都直接使用全局變量。

　　很多成熟的產品也處處體現著計算復用的思想，如在PHP中，下面代碼可以得到一個數組的元素個數：

　　如果我們來實現，最自然的想法就是遍歷數組。但是PHP的開發者明顯更聰明，他們在建立數組時同時建立一個與之關聯的內部的數量計數變量（對PHP程序員透明），隨著數組元素的增減，這個變量也相應增減，每次調用count函數直接返回這個變量即可，這就將count的復雜度從O(n)降為O(1)，這也是計算復用的一個典型應用。

　　另外，其實計算復用和緩存的概念是相通的，很多緩存系統就使用了計算復用的思想。