程序設(shè)計中的計算復用(Computational Reuse)
程序設(shè)計(Programming)是給出解決特定問題程序的過程，是軟件構(gòu)造活動中的重要組成部分。程序設(shè)計往往以某種程序設(shè)計語言為工具，給出這種語言下的程序。程序設(shè)計過程應當包括分析、設(shè)計、編碼、測試、排錯等不同階段。本文介紹的是程序設(shè)計中的計算復用，希望能給你帶來幫助。
從斐波那契數(shù)列說起
我想幾乎每一個程序員對斐波那契（Fibonacci）數(shù)列都不會陌生，在很多教科書或文章中涉及到遞歸或計算復雜性的地方都會將計算斐波那契數(shù)列的程序作為經(jīng)典示例。如果現(xiàn)在讓你以最快的速度用C#寫出一個計算斐波那契數(shù)列第n個數(shù)的函數(shù)（不考慮參數(shù)小于1或結(jié)果溢出等異常情況），我不知你的程序是否會和下列代碼類似：
- public static ulong Fib(ulong n)
- {
- return (n == 1 || n == 2) ? 1 : Fib(n - 1) + Fib(n - 2);
- }
這段代碼應該算是短小精悍（執(zhí)行代碼只有一行），直觀清晰，而且非常符合許多程序員的代碼美學，許多人在面試時寫出這樣的代碼可能心里還會暗爽。但是如果用這段代碼試試計算Fib(100)我想就再也爽不起來了，估計下星期甚至下個月前結(jié)果很難算得出來。
看來好看的代碼未必中用，如果程序在效率不能接受那美觀神馬的就都是浮云了。如果簡單分析一下程序的執(zhí)行流，就會發(fā)現(xiàn)問題在哪，以計算Fibonacci(5)為例：
從上圖可以看出，在計算Fib(5)的過程中，F(xiàn)ib(1)計算了兩次、Fib(2)計算了3次，F(xiàn)ib(3)計算了兩次，本來只需要5次計算就可以完成的任務卻計算了9次。這個問題隨著規(guī)模的增加會愈發(fā)凸顯，以至于Fib(100)已經(jīng)無法再可接受的時間內(nèi)算出。雖然可以通過尾遞歸優(yōu)化將雙遞歸變?yōu)閱芜f歸，但是效果也并不理想。
這是一個非常典型的忽視“計算復用”的例子。計算復用的目標在于保證計算過程中同一計算子過程只進行一次，通過保存子過程計算結(jié)果并復用來提高計算效率。其實類似上面的代碼出現(xiàn)在很多教科書中，如果是為了展示斐波那契數(shù)列的數(shù)學特性當然無可厚非，但是作為計算機程序就很有問題了。
因為數(shù)學和計算科學是有區(qū)別的，數(shù)學要求嚴謹和簡潔的表達，而計算科學則需要盡量快的得出結(jié)果，好的數(shù)學公式未必是好的計算公式。這也說明程序設(shè)計不是簡單的將數(shù)學語言翻譯為計算機語言就可以了，程序員應該能將數(shù)學語言首先翻譯成計算科學語言（算法？），然后再翻譯成機器語言。因此程序員的工作絕不是機械的，而是要有一定的創(chuàng)造性，所以必要的算法知識對程序員至關(guān)重要，因為算法教會程序員如何用最有效率的方式去編寫程序。
言歸正傳，根據(jù)以上分析，可以寫出一個更高效的斐波那契數(shù)列計算程序：
- 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;
- }
這段代碼可能看起來不如上一段那么優(yōu)美，但是其效率卻是***段代碼不可比擬的。例如計算Fib(40)，在我的機器上，***段代碼用時3.5秒，而第二段代碼小于0.001秒。這個差距隨著規(guī)模增大會更明顯，例如Fib(100)，***段代碼可能需要幾天甚至幾周，而第二段代碼耗時仍然小于0.001秒。天壤之別！
如果從計算復雜性的角度分析，***段代碼的復雜度為O(1.6^n)，對數(shù)學敏感的朋友應該能體會到這個函數(shù)可怕的增長速度，這甚至不是一個多項式級別的復雜度，而第二段代碼僅為O(n)。看到如此簡單一個例子出現(xiàn)如此差別，還能說程序員學習算法沒有用嗎。
上面代碼對于“計算復用”的思想體現(xiàn)不是很明顯，因為我們僅僅需要一個結(jié)果，中間結(jié)果都被丟棄了，如果是計算1<=i<=n的所有Fib(i)，那么計算復用的思想就會體現(xiàn)的比較明顯。
矩陣乘法與Strassen算法
下面說一個將計算復用發(fā)揮到***的例子，說實話直到現(xiàn)在每次看到Strassen算法我都覺得震撼，不知Strassen當年是長了何等天才的腦子才發(fā)現(xiàn)這么漂亮的一個算法。
矩陣計算在許多領(lǐng)域如機器學習、圖形圖像處理、模式識別中均占有重要地位。而計算兩個n*n矩陣乘積的運算是矩陣計算中常見的計算。由矩陣理論可知，普通方法計算兩個n階方陣的乘積需要進行n^3次乘法計算，其計算復雜度自然是O(n^3)。但是德國數(shù)學家Volker Strassen通過拆分矩陣并復用計算結(jié)果，發(fā)現(xiàn)了一種復雜度為O(n^2.81)的算法，這個算法簡單說來如下。
假設(shè)n為2的冪（不為2的冪也能計算，這里是為了方便說明），A和B是兩個n階方陣，則A和B分別可以分解成4個n/2階方陣：
則：
可惜這樣經(jīng)過8次n/2階方陣相乘，復雜度還是O(n^3)，沒有降低復雜度。天才的Volker Strassen發(fā)現(xiàn)了一種通過計算7次n/2階方陣來得出n階方陣乘積的方法。具體來說，假設(shè)每個矩陣的積可以寫成如下形式：
然后設(shè)：
這樣通過7次n/2矩陣的相乘計算出P1-P7，然后：
這樣就組合出了AB，這個方法的復雜度為O(n^2.81)，這個算法實在是太漂亮了。天才！絕對的天才啊！對于這種人除了無限崇敬我真是沒有其它想法了，能將計算復用發(fā)揮到如此境地，不知世間能有幾人。
計算復用對軟件開發(fā)的啟示
也許有的朋友會說，“我又不開發(fā)數(shù)值計算型程序，也不會接觸如此復雜的算法，計算復用與我何干？”。實際上即使開發(fā)非數(shù)值型程序，計算復用的思想也是大有用途的。例如我曾經(jīng)在一個真實的PHP開發(fā)的行業(yè)系統(tǒng)中見過類似這樣的代碼：
- foreach($items as $k => $v){
- //...
- $money = $v->money + getTax();
- //...
- }
當時我問開發(fā)這個程序的人這里getTax的返回值和每個item有關(guān)系嗎，他說稅費是一套復雜的算法算出來的，但是其值固定的。那這里可就太浪費了，每次循環(huán)都計算一次，如果改為如下：
- $tax = getTax();
- foreach($items as $k => $v){
- //...
- $money = $v->money + $tax;
- //...
- }
則可以節(jié)省不少計算資源。在后來的溝通中發(fā)現(xiàn)這個問題原來是重構(gòu)的遺留問題，以前系統(tǒng)中的稅率計算是寫在程序里的，后來發(fā)現(xiàn)這個計算越來越多，就使用“Extract Method”重構(gòu)模式提取成了getTax函數(shù)，但是這樣的后果就是到處都是getTax調(diào)用，有的程序段甚至調(diào)用七八次，但是如果應用計算復用的思想，則應該在腳本開始只計算一次稅費并保存，后面全都使用這個變量而不是每次調(diào)用getTax。
總之，只要某個計算結(jié)果與執(zhí)行上下文無關(guān)，并且在一個執(zhí)行流中超過一次被使用，則應該使用計算復用。
這個例子還算明顯的，有時可能不會這么明顯，例如我們知道JavaScript中從深層函數(shù)中引用全局對象的代價是很高的，因為需要遍歷作用域鏈（當然是隱式的），因此在JS中如果深層函數(shù)代碼頻繁使用全局對象，則要付出很高的代價。如果程序員不懂得對象及作用域鏈相關(guān)知識，則不會發(fā)現(xiàn)這種潛在的效率問題，而正確的做法是使用一個局部變量保存對全局對象的引用而不是每次都直接使用全局變量。
很多成熟的產(chǎn)品也處處體現(xiàn)著計算復用的思想，如在PHP中，下面代碼可以得到一個數(shù)組的元素個數(shù)：
- echo count($arr);
如果我們來實現(xiàn)，最自然的想法就是遍歷數(shù)組。但是PHP的開發(fā)者明顯更聰明，他們在建立數(shù)組時同時建立一個與之關(guān)聯(lián)的內(nèi)部的數(shù)量計數(shù)變量（對PHP程序員透明），隨著數(shù)組元素的增減，這個變量也相應增減，每次調(diào)用count函數(shù)直接返回這個變量即可，這就將count的復雜度從O(n)降為O(1)，這也是計算復用的一個典型應用。
另外，其實計算復用和緩存的概念是相通的，很多緩存系統(tǒng)就使用了計算復用的思想。
原文連接：http://www.cnblogs.com/leoo2sk/archive/2011/03/03/computational-reuse.html
【編輯推薦】
