作為程序員，開發(fā)完一段代碼，實(shí)現(xiàn)了某個(gè)功能時(shí)，有必要知道：

我的程序需要多長時(shí)間？

是什么導(dǎo)致我的程序消耗很多內(nèi)存？

比如，統(tǒng)計(jì)或者處理了一大批數(shù)據(jù)。影響這些問題的因素很多，例如，電腦的性能，數(shù)據(jù)的性質(zhì)（值類型和引用類型的區(qū)別），使用的算法。想要為這些基礎(chǔ)問題提供答案需要通過科學(xué)方法。

1. 什么是科學(xué)方法？？

它是科學(xué)家為獲取自然界知識所使用的一系列大家認(rèn)同的方法。

• 1. 細(xì)致地觀察真實(shí)世界的特點(diǎn)，通常還要精確的測量
• 2. 根據(jù)觀察結(jié)果提出假設(shè)模型
• 3. 根據(jù)模型預(yù)測未來的事件
• 4. 繼續(xù)觀察并核實(shí)預(yù)測的準(zhǔn)確性
• 5. 如此反復(fù)直到確認(rèn)預(yù)測和觀察一致

這里我們不需要深究它，我們會(huì)使用數(shù)學(xué)分析（科學(xué)方法的一種）為算法成本建立模型，并使用實(shí)驗(yàn)數(shù)據(jù)驗(yàn)證這些模型。

科學(xué)方法的一條關(guān)鍵原則是可重現(xiàn)的，可證偽的。

1.觀察

怎么定量測量程序的運(yùn)行時(shí)間？
各種工具，谷歌瀏覽器...，計(jì)時(shí)器 Stopwatch
我們一般只需要近似值就可以了。
對大多數(shù)程序的第一個(gè)定量觀察就是計(jì)算性任務(wù)的困難程度可以用問題的規(guī)模來衡量。什么是問題的規(guī)模？可以是輸入的大小或是某個(gè)命令行參數(shù)的值（開發(fā)預(yù)估時(shí)間）。
另一個(gè)定量觀察是運(yùn)行時(shí)長和輸入本身相對無關(guān)，它主要取決于問題模型。就是說，同樣大小的輸入量，程序運(yùn)行時(shí)間是差不多的。如果換一批同樣大小的數(shù)據(jù)，運(yùn)行時(shí)長差很多，就需要控制運(yùn)行時(shí)間對輸入的敏感度（比如把實(shí)驗(yàn)數(shù)據(jù)存起來）。

2.將問題規(guī)模和運(yùn)行時(shí)間的關(guān)系量化

• 1.生成實(shí)驗(yàn)數(shù)據(jù)
• 2. 數(shù)據(jù)分析

根據(jù)問題規(guī)模和運(yùn)行時(shí)長的數(shù)據(jù)繪制圖表
猜想

舉例 ThreeSum 實(shí)驗(yàn)

public static int ThreeSum(int[] a)
        {
            int N = a.Length;
            int cnt = 0;
            for (var i = 0; i < N; i++)
            {
                for (var j = i+1; j < N; j++)
                {
                    for (var k = j + 1; k < N; k++)
                    {
                        if(a[i]+a[j]+a[k] == 0)
                        {
                            cnt++;
                        }
                    }
                }
            }

            return cnt;
        }

lg(T(N)) = 3 lgN + lga --a是常數(shù)
T(N) = aN^3
這里猜想的時(shí)候用到冥次法則：T(N) = aN^b

2.數(shù)學(xué)模型

雖然有很多復(fù)雜的因素影響著程序的運(yùn)行時(shí)間，但一個(gè)程序的運(yùn)行的總時(shí)間主要有關(guān)的兩點(diǎn)是：

• 1. 執(zhí)行每條語句的時(shí)長 （取決于計(jì)算機(jī)，編譯器和操作系統(tǒng)）
• 2. 執(zhí)行每條語句的頻率 （取決于程序本身和輸入）

計(jì)算執(zhí)行每條語句的時(shí)長可以通過各種工具測出。

重點(diǎn)是判斷執(zhí)行每條語句的執(zhí)行頻率，有的語句很好判斷，比如一些賦值語句；有些需要深入分析，比如ThreeSum 實(shí)驗(yàn)中 if 語句的執(zhí)行次數(shù)為 N(N-1)(N-2) / 6 次（主要是要了解立方推導(dǎo)公式）。而且有些語句的執(zhí)行次數(shù)取決于輸入的數(shù)據(jù)，例如 計(jì)算和為 0 的三元組的數(shù)量的語句（0 ~ N^3 / 6）。

近似

頻率分析可能會(huì)產(chǎn)生復(fù)雜冗長的數(shù)學(xué)表達(dá)式，例如：

N(N-1)(N-2) / 6 = N^3 / 6 - N^2 / 2 + N/3

我們使用波浪號逼近法，在其中我們丟棄使公式復(fù)雜化的低階項(xiàng)。我們寫?f（N）表示當(dāng)N增長時(shí)除以f（N）接近1的任何函數(shù)。我們寫g（N）?f（N）表示當(dāng)N增長時(shí)g（N）/ f（N）接近1。

所以N^3 / 6 - N^2 / 2 + N/3 的 近似函數(shù)是N^3 / 6 ，增長數(shù)量級 是N^3 。

近似運(yùn)行時(shí)間

大部分情況下，執(zhí)行最頻繁的語句決定了程序執(zhí)行的總時(shí)間 - 內(nèi)循環(huán)，ThreeSum 實(shí)驗(yàn)中的內(nèi)循環(huán)就是 第三層循環(huán)和 if 語句。大部分程序的運(yùn)行時(shí)間都只取決于某一小部分。

性質(zhì)（猜想）：ThreeSum 的運(yùn)行時(shí)間 ~ aN^3 （a 是常數(shù)），增長數(shù)量級是N^3。

成本模型

定義了所研究的算法的基本操作。

可以用一個(gè)成本模型來評估算法的性質(zhì)。在這個(gè)成本模型下，我們可以用數(shù)字說明算法而非某個(gè)性質(zhì)。

例如，ThreeSum 的成本模型是數(shù)組的訪問次數(shù)（無論讀寫）。

性質(zhì)：該算法訪問了 ~ N^3 / 6 個(gè)整數(shù)三元組中的所有3個(gè)整數(shù)。

通過明確成本模型使給定程序所需的運(yùn)行時(shí)間的增長數(shù)量級和程序算法真正成本的增長數(shù)量級相同。

總結(jié)

大多數(shù)程序，得到運(yùn)行時(shí)間的數(shù)學(xué)模型所需的步驟：

• 1. 確定輸入模型，定義問題的模型（該任務(wù)的困難程度）
• 2. 識別內(nèi)循環(huán)
• 3. 根據(jù)內(nèi)循環(huán)中的操作確定成本模型
• 4. 對于給定的輸入，判斷這些操作的執(zhí)行頻率

3. 增長數(shù)量級的分類

我們使用一些結(jié)構(gòu)原語（普通語句，條件，循環(huán)，嵌套和方法調(diào)用）來實(shí)現(xiàn)算法，因此，成本增長的數(shù)量級通常是問題規(guī)模N的幾個(gè)函數(shù)之一。

4. 倍率實(shí)驗(yàn)

步驟：

1.循環(huán)執(zhí)行ThreeSum 方法，并且每次 N = 2 * N （2 是比例，可以調(diào)整）

2. 打印每次執(zhí)行ThreeSum 方法的運(yùn)行時(shí)長和上一次的比

3. 直到該比值趨近于 2^b （b 是常數(shù)）

public static void RatioTest()
        {
            Random rd = new Random();
            Stopwatch timer = new Stopwatch();
            int[] a = new int[125];
            for (var i = 0; i < 125; i++)
            {
                a[i] = rd.Next(-1000, 1000);
            }

            timer.Start();
            var res = ThreeSum(a);
            timer.Stop();
            var prev = timer.ElapsedMilliseconds;

            for (var N = 250; true; N = 2*N)
            {
                a = new int[N];
                for (var i = 0; i < N; i++)
                {
                    a[i] = rd.Next(-1000, 1000);
                }
                timer.Start();
                var _res = ThreeSum(a);
                timer.Stop();
                var time = timer.ElapsedMilliseconds;
                var ratio = (decimal)time / prev;
                //Console.WriteLine(a.Length + "\t" + time + "\t" + ratio);
                Console.WriteLine(ratio);
                prev = time;
                //Thread.Sleep(1000);
            }
        }

根據(jù)冥次法則公式可以推導(dǎo)出該比例是以 2 為底的對數(shù)。并且可以得出增長數(shù)量級的近似模型（N^b）：

a 為 比例數(shù)， c 為極限比值， b 為該算法增長數(shù)量級的指數(shù)。這里 b = 3。

這個(gè)實(shí)驗(yàn)對于比值沒有極限的算法無效。

該方法可以簡單地預(yù)測程序地性能并判斷它們的運(yùn)行時(shí)間大致的增長數(shù)量級。

使用該方法可以評估解決大型問題的可行性，比如可以預(yù)估一個(gè)大型問題的程序運(yùn)行時(shí)間。同時(shí)也可以評估使用更快的計(jì)算機(jī)所運(yùn)行的時(shí)間。

5.注意事項(xiàng)

在對程序的性能進(jìn)行分析時(shí)，得到不一致或者有誤導(dǎo)性的結(jié)果的原因有很多：

1.大常數(shù)

在去近似時(shí)，我們一般會(huì)忽略低階項(xiàng)，但如果低階項(xiàng)的系數(shù)很大時(shí)（例如 10^3 或 10^6），該近似就是錯(cuò)誤的。所以我們要對可能的大常數(shù)敏感。

2. 非決定性的內(nèi)循環(huán)

內(nèi)循環(huán)是決定性因素的假設(shè)并不總是正確的。錯(cuò)誤的成本模型可能無法得到真正的內(nèi)循環(huán)，問題的規(guī)模也許沒有大到對指令的執(zhí)行頻率的首項(xiàng)大大超過其他低階項(xiàng)并可以忽略他們的程度。有些程序在內(nèi)循環(huán)之外也有大量指令需要考慮。換句話說，成本模型需要改進(jìn)。

3. 指令時(shí)間

由于大多數(shù)計(jì)算機(jī)系統(tǒng)都會(huì)使用緩存技術(shù)，所以每條執(zhí)行所需的時(shí)間并不是總是相同。

4. 系統(tǒng)因素

如果計(jì)算機(jī)同時(shí)運(yùn)行很多程序，會(huì)產(chǎn)生爭奪資源的情況，這會(huì)影響實(shí)驗(yàn)結(jié)果。

5. 對輸入的強(qiáng)烈依賴

在研究程序的運(yùn)行時(shí)間的增長數(shù)量級時(shí)，我假設(shè)運(yùn)行時(shí)間和輸入相對無關(guān)。當(dāng)這個(gè)條件不滿足時(shí)，會(huì)得到不一致或者錯(cuò)誤的結(jié)果。例如，ThreeSum 返回的不是三個(gè)整數(shù)為0的對數(shù)，而是是否存在。如果前三個(gè)整數(shù)就滿足，該程序的運(yùn)行時(shí)間的增長數(shù)量級為常數(shù)；如果輸入不含有這樣的三個(gè)整數(shù)，程序的運(yùn)行時(shí)間的增長量級為立方級別。

6. 多個(gè)問題參量

ThreeSum 性能分析是僅需要一個(gè)參量的函數(shù)來衡量程序的性能，參量一般是輸入的規(guī)模。但是，多個(gè)參量也是有可能的。例如白名單（一個(gè)整數(shù)列表 M 個(gè)，一個(gè)白名單整數(shù)列表 N個(gè)，返回整數(shù)列表中有多少個(gè)整數(shù)在白名單中存在）,運(yùn)行時(shí)間一般和 M logN 成正比。

6. 處理對于輸入的依賴

輸入模型： 我們可以仔細(xì)模擬要處理的輸入的種類。這種方法具有挑戰(zhàn)性，因?yàn)樵撃Ｐ涂赡苁遣滑F(xiàn)實(shí)的。

最壞情況下的性能保證：不管輸入什么，程序的運(yùn)行時(shí)間都小于一定的范圍（取決于輸入大小）。這種保守的方法可能適用于運(yùn)行核反應(yīng)堆或心臟起搏器或汽車制動(dòng)器的軟件。

隨機(jī)算法：提供性能保證的一種方法是引入隨機(jī)性，例如快速排序和哈希。每次您運(yùn)行算法時(shí)，都會(huì)花費(fèi)不同的時(shí)間。這些保證不是絕對的，但是它們無效的機(jī)會(huì)小于您的計(jì)算機(jī)被閃電擊中的機(jī)會(huì)。因此，這種保證在實(shí)踐中與最壞情況的保證一樣有用。

操作序列：對于許多應(yīng)用程序，算法輸入可能不僅是數(shù)據(jù)，還包括客戶端執(zhí)行的操作順序。

均攤分析： 提供性能保證的另一種方法是通過記錄所有操作的總成本并除以操作總數(shù)來將成本均攤。

7.內(nèi)存

計(jì)算程序?qū)?nèi)存的使用情況和運(yùn)行時(shí)間一樣重要。計(jì)算機(jī)中電路的很大一部分作用就是幫助應(yīng)用程序保存一些值并在使用時(shí)取出。保存的值越多，需要的電路越多，需要的內(nèi)存也越多。

.net 內(nèi)存分配系統(tǒng)已經(jīng)幫我們解決了內(nèi)存問題。

.net 使用 8 位（64位）表示字節(jié)，每個(gè)基本類型需要的內(nèi)存：

1. 對象

一個(gè)對象所使用的內(nèi)存，需要將所有實(shí)例變量使用內(nèi)存與對象本身的開銷（一般是16字節(jié)，這些開銷包括一個(gè)指向?qū)ο蟮念惖囊茫厥招畔⒑屯叫畔ⅲ┮约?個(gè)填充字節(jié)相加。

當(dāng)我們說一個(gè)引用所占的內(nèi)存時(shí)，指的是它所指向的對象所占的內(nèi)存。對象的引用通常是一個(gè)內(nèi)存地址，因此使用8個(gè)字節(jié)的內(nèi)存（在64位計(jì)算機(jī)上）。

2. 鏈表

嵌套的非靜態(tài)類需要額外的8字節(jié)。例如，如果 Node 類是嵌套類，基于鏈表的棧中一個(gè)Node對象需要 40 字節(jié)（16字節(jié)的對象開銷，兩個(gè)對象引用各需8字節(jié)，還有8字節(jié)的額外開銷。為什么不需要填充字節(jié)）。

因?yàn)橐粋€(gè) Integer 對象需要24字節(jié)，所以一個(gè)含有 N 個(gè)整數(shù)的基于鏈表的表需要 32 + 64 N 字節(jié)（Stack 對象開銷 16 字節(jié)，引用類型實(shí)例變量 8 字節(jié)，int 類型實(shí)例變量 4 字節(jié)，4個(gè)填充字節(jié)，每個(gè)元素64字節(jié)（一個(gè) Node 對象40字節(jié)和一個(gè)Integer 對象 24 字節(jié)））

3. 數(shù)組

C# 中數(shù)組是引用類型，一般都會(huì)因?yàn)橛涗涢L度需要額外的內(nèi)存。一個(gè)基礎(chǔ)類型的數(shù)組一般需要24字節(jié)的頭信息（16字節(jié)的對象開銷，4字節(jié)用于保存長度以及4填充字節(jié)）再加上保存值所需的內(nèi)存。例如一個(gè) 含有 N個(gè) int 值的數(shù)組需要 24 + 4N (會(huì)被填充為 8 的倍數(shù))

4. 字符串對象

String 的標(biāo)準(zhǔn)實(shí)現(xiàn)含有4個(gè)實(shí)例變量：一個(gè)指向字符數(shù)組的引用（8字節(jié)）和三個(gè) int 值（各4字節(jié)）。第一個(gè) int 值描述的是字符數(shù)組中的偏移量，第二個(gè) int 值是字符串的長度。第三個(gè)值是一個(gè)散列值，它在某些情況下可以節(jié)省計(jì)算?？偣残枰?0字節(jié)，這是除字符數(shù)組之外字符串所需的內(nèi)存空間，加上字符數(shù)組的話是 40 + 24 + 2N = 64 + 2N。

但是，字符數(shù)組常常是在多個(gè)字符串之間共享的。因?yàn)?String 對象是不可變的，這種設(shè)計(jì)使 String 的實(shí)現(xiàn)能夠在多個(gè)String對象中都含有相同的字符數(shù)組時(shí)節(jié)省內(nèi)存。

當(dāng)使用 SubString 創(chuàng)建了一個(gè)新的 String 對象（40字節(jié)），但它仍重用了相同的字符數(shù)組。

當(dāng)涉及到函數(shù)調(diào)用時(shí)， 內(nèi)存的消耗是一個(gè)復(fù)雜的動(dòng)態(tài)過程。當(dāng)調(diào)用一個(gè)方法時(shí)，系統(tǒng)會(huì)從內(nèi)存中的一個(gè)特定區(qū)域?yàn)榉椒ǚ峙渌璧膬?nèi)存（用于保存局部變量），這個(gè)區(qū)域叫做棧。當(dāng)方法返回時(shí)，占用的內(nèi)存將被返回給棧，所以，在遞歸調(diào)用中不要?jiǎng)?chuàng)建大型的對象。當(dāng)使用 new 創(chuàng)建對象時(shí)，系統(tǒng)會(huì)在堆中分配所需的內(nèi)存，而且對象會(huì)一直存在，知道沒有任何對它的引用。

到此這篇關(guān)于C#算法設(shè)計(jì)與分析的文章就介紹到這了。希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評論