九九热这里直有精品,1区二区三区在线播放,玖玖爱在线观看资源,国产aⅴ综合网,午夜福利男女,日本亚洲欧美三级,日韩无码黄色导航,内射少妇13区,中文字幕高清网

從斐波那契數(shù)列說起

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

public static ulong Fib(ulong n)

{

    return (n == 1 || n == 2) ? 1 : Fib(n - 1) + Fib(n - 2);

}

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

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

　　從上圖可以看出，在計(jì)算Fib(5)的過程中，F(xiàn)ib(1)計(jì)算了兩次、Fib(2)計(jì)算了3次，F(xiàn)ib(3)計(jì)算了兩次，本來只需要5次計(jì)算就可以完成的任務(wù)卻計(jì)算了9次。這個(gè)問題隨著規(guī)模的增加會(huì)愈發(fā)凸顯，以至于Fib(100)已經(jīng)無法再可接受的時(shí)間內(nèi)算出。雖然可以通過尾遞歸優(yōu)化將雙遞歸變?yōu)閱芜f歸，但是效果也并不理想。

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

　　言歸正傳，根據(jù)以上分析，可以寫出一個(gè)更高效的斐波那契數(shù)列計(jì)算程序：

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)美，但是其效率卻是第一段代碼不可比擬的。例如計(jì)算Fib(40)，在我的機(jī)器上，第一段代碼用時(shí)3.5秒，而第二段代碼小于0.001秒。這個(gè)差距隨著規(guī)模增大會(huì)更明顯，例如Fib(100)，第一段代碼可能需要幾天甚至幾周，而第二段代碼耗時(shí)仍然小于0.001秒。天壤之別！

　　如果從計(jì)算復(fù)雜性的角度分析，第一段代碼的復(fù)雜度為O(1.6^n)，對(duì)數(shù)學(xué)敏感的朋友應(yīng)該能體會(huì)到這個(gè)函數(shù)可怕的增長(zhǎng)速度，這甚至不是一個(gè)多項(xiàng)式級(jí)別的復(fù)雜度，而第二段代碼僅為O(n)?？吹饺绱撕?jiǎn)單一個(gè)例子出現(xiàn)如此差別，還能說程序員學(xué)習(xí)算法沒有用嗎。

　　上面代碼對(duì)于“計(jì)算復(fù)用”的思想體現(xiàn)不是很明顯，因?yàn)槲覀儍H僅需要一個(gè)結(jié)果，中間結(jié)果都被丟棄了，如果是計(jì)算1<=i<=n的所有Fib(i)，那么計(jì)算復(fù)用的思想就會(huì)體現(xiàn)的比較明顯。

　　矩陣乘法與Strassen算法

　　下面說一個(gè)將計(jì)算復(fù)用發(fā)揮到極致的例子，說實(shí)話直到現(xiàn)在每次看到Strassen算法我都覺得震撼，不知Strassen當(dāng)年是長(zhǎng)了何等天才的腦子才發(fā)現(xiàn)這么漂亮的一個(gè)算法。

　　矩陣計(jì)算在許多領(lǐng)域如機(jī)器學(xué)習(xí)、圖形圖像處理、模式識(shí)別中均占有重要地位。而計(jì)算兩個(gè)n*n矩陣乘積的運(yùn)算是矩陣計(jì)算中常見的計(jì)算。由矩陣?yán)碚摽芍?，普通方法?jì)算兩個(gè)n階方陣的乘積需要進(jìn)行n^3次乘法計(jì)算，其計(jì)算復(fù)雜度自然是O(n^3)。但是德國數(shù)學(xué)家Volker Strassen通過拆分矩陣并復(fù)用計(jì)算結(jié)果，發(fā)現(xiàn)了一種復(fù)雜度為O(n^2.81)的算法，這個(gè)算法簡(jiǎn)單說來如下。

　　假設(shè)n為2的冪（不為2的冪也能計(jì)算，這里是為了方便說明），A和B是兩個(gè)n階方陣，則A和B分別可以分解成4個(gè)n/2階方陣：

　　則：

　　可惜這樣經(jīng)過8次n/2階方陣相乘，復(fù)雜度還是O(n^3)，沒有降低復(fù)雜度。天才的Volker Strassen發(fā)現(xiàn)了一種通過計(jì)算7次n/2階方陣來得出n階方陣乘積的方法。具體來說，設(shè)：

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

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

　　計(jì)算復(fù)用對(duì)軟件開發(fā)的啟示

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

foreach($items as $k => $v){

    //...

    $money = $v->money + getTax();

    //...

}

　　當(dāng)時(shí)我問開發(fā)這個(gè)程序的人這里getTax的返回值和每個(gè)item有關(guān)系嗎，他說稅費(fèi)是一套復(fù)雜的算法算出來的，但是其值固定的。那這里可就太浪費(fèi)了，每次循環(huán)都計(jì)算一次，如果改為如下：

$tax = getTax();

foreach($items as $k => $v){

    //...

    $money = $v->money + $tax;

    //...

}

　　則可以節(jié)省不少計(jì)算資源。在后來的溝通中發(fā)現(xiàn)這個(gè)問題原來是重構(gòu)的遺留問題，以前系統(tǒng)中的稅率計(jì)算是寫在程序里的，后來發(fā)現(xiàn)這個(gè)計(jì)算越來越多，就使用“Extract Method”重構(gòu)模式提取成了getTax函數(shù)，但是這樣的后果就是到處都是getTax調(diào)用，有的程序段甚至調(diào)用七八次，但是如果應(yīng)用計(jì)算復(fù)用的思想，則應(yīng)該在腳本開始只計(jì)算一次稅費(fèi)并保存，后面全都使用這個(gè)變量而不是每次調(diào)用getTax。

　　總之，只要某個(gè)計(jì)算結(jié)果與執(zhí)行上下文無關(guān)，并且在一個(gè)執(zhí)行流中超過一次被使用，則應(yīng)該使用計(jì)算復(fù)用。

　　這個(gè)例子還算明顯的，有時(shí)可能不會(huì)這么明顯，例如我們知道JavaScript中從深層函數(shù)中引用全局對(duì)象的代價(jià)是很高的，因?yàn)樾枰闅v作用域鏈（當(dāng)然是隱式的），因此在JS中如果深層函數(shù)代碼頻繁使用全局對(duì)象，則要付出很高的代價(jià)。如果程序員不懂得對(duì)象及作用域鏈相關(guān)知識(shí)，則不會(huì)發(fā)現(xiàn)這種潛在的效率問題，而正確的做法是使用一個(gè)局部變量保存對(duì)全局對(duì)象的引用而不是每次都直接使用全局變量。

　　很多成熟的產(chǎn)品也處處體現(xiàn)著計(jì)算復(fù)用的思想，如在PHP中，下面代碼可以得到一個(gè)數(shù)組的元素個(gè)數(shù)：

echo count($arr);

　　如果我們來實(shí)現(xiàn)，最自然的想法就是遍歷數(shù)組。但是PHP的開發(fā)者明顯更聰明，他們?cè)诮?shù)組時(shí)同時(shí)建立一個(gè)與之關(guān)聯(lián)的內(nèi)部的數(shù)量計(jì)數(shù)變量（對(duì)PHP程序員透明），隨著數(shù)組元素的增減，這個(gè)變量也相應(yīng)增減，每次調(diào)用count函數(shù)直接返回這個(gè)變量即可，這就將count的復(fù)雜度從O(n)降為O(1)，這也是計(jì)算復(fù)用的一個(gè)典型應(yīng)用。

　　另外，其實(shí)計(jì)算復(fù)用和緩存的概念是相通的，很多緩存系統(tǒng)就使用了計(jì)算復(fù)用的思想。