C#演演算法設計與分析詳解

2022-04-15 16:00:39

1. 什麼是科學方法？？

它是科學家為獲取自然界知識所使用的一系列大家認同的方法。

1. 細緻地觀察真實世界的特點，通常還要精確的測量
2. 根據觀察結果提出假設模型
3. 根據模型預測未來的事件
4. 繼續觀察並核實預測的準確性
5. 如此反覆直到確認預測和觀察一致

這裡我們不需要深究它，我們會使用數學分析（科學方法的一種）為演演算法成本建立模型，並使用實驗資料驗證這些模型。

科學方法的一條關鍵原則是可重現的，可證偽的。

1.觀察

怎麼定量測量程式的執行時間？
各種工具，谷歌瀏覽器...，計時器 Stopwatch
我們一般只需要近似值就可以了。
對大多數程式的第一個定量觀察就是計算性任務的困難程度可以用問題的規模來衡量。什麼是問題的規模？可以是輸入的大小或是某個命令列引數的值（開發預估時間）。
另一個定量觀察是執行時長和輸入本身相對無關，它主要取決於問題模型。就是說，同樣大小的輸入量，程式執行時間是差不多的。如果換一批同樣大小的資料，執行時長差很多，就需要控制執行時間對輸入的敏感度（比如把實驗資料存起來）。

2.將問題規模和執行時間的關係量化

1.生成實驗資料
2. 資料分析

根據問題規模和執行時長的資料繪製圖表
猜想

舉例 ThreeSum 實驗

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是常數
T(N) = aN^3
這裡猜想的時候用到冥次法則：T(N) = aN^b

2.數學模型

雖然有很多複雜的因素影響著程式的執行時間，但一個程式的執行的總時間主要有關的兩點是：

1. 執行每條語句的時長（取決於計算機，編譯器和作業系統）
2. 執行每條語句的頻率（取決於程式本身和輸入）

計算執行每條語句的時長可以通過各種工具測出。

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

近似

頻率分析可能會產生複雜冗長的數學表示式，例如：

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

我們使用波浪號逼近法，在其中我們丟棄使公式複雜化的低階項。我們寫〜f（N）表示當N增長時除以f（N）接近1的任何函數。我們寫g（N）〜f（N）表示當N增長時g（N）/ f（N）接近1。

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

近似執行時間

大部分情況下，執行最頻繁的語句決定了程式執行的總時間 - 內迴圈，ThreeSum 實驗中的內迴圈就是第三層迴圈和 if 語句。大部分程式的執行時間都只取決於某一小部分。

性質（猜想）：ThreeSum 的執行時間 ~ aN^3 （a 是常數），增長數量級是N^3。

成本模型

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

可以用一個成本模型來評估演演算法的性質。在這個成本模型下，我們可以用數位說明演演算法而非某個性質。

例如，ThreeSum 的成本模型是陣列的存取次數（無論讀寫）。

性質：該演演算法存取了 ~ N^3 / 6 個整數三元組中的所有3個整數。

通過明確成本模型使給定程式所需的執行時間的增長數量級和程式演演算法真正成本的增長數量級相同。

總結

大多數程式，得到執行時間的數學模型所需的步驟：

1. 確定輸入模型，定義問題的模型（該任務的困難程度）
2. 識別內迴圈
3. 根據內迴圈中的操作確定成本模型
4. 對於給定的輸入，判斷這些操作的執行頻率

3. 增長數量級的分類

我們使用一些結構原語（普通語句，條件，迴圈，巢狀和方法呼叫）來實現演演算法，因此，成本增長的數量級通常是問題規模N的幾個函數之一。

4. 倍率實驗

步驟：

1.迴圈執行ThreeSum 方法，並且每次 N = 2 * N （2 是比例，可以調整）

2. 列印每次執行ThreeSum 方法的執行時長和上一次的比

3. 直到該比值趨近於 2^b （b 是常數）

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);
            }
        }

根據冥次法則公式可以推匯出該比例是以 2 為底的對數。並且可以得出增長數量級的近似模型（N^b）：

a 為比例數， c 為極限比值， b 為該演演算法增長數量級的指數。這裡 b = 3。

這個實驗對於比值沒有極限的演演算法無效。

該方法可以簡單地預測程式地效能並判斷它們的執行時間大致的增長數量級。

使用該方法可以評估解決大型問題的可行性，比如可以預估一個大型問題的程式執行時間。同時也可以評估使用更快的計算機所執行的時間。

5.注意事項

在對程式的效能進行分析時，得到不一致或者有誤導性的結果的原因有很多：

1.大常數

在去近似時，我們一般會忽略低階項，但如果低階項的係數很大時（例如 10^3 或 10^6），該近似就是錯誤的。所以我們要對可能的大常數敏感。

2. 非決定性的內迴圈

內迴圈是決定性因素的假設並不總是正確的。錯誤的成本模型可能無法得到真正的內迴圈，問題的規模也許沒有大到對指令的執行頻率的首項大大超過其他低階項並可以忽略他們的程度。有些程式在內迴圈之外也有大量指令需要考慮。換句話說，成本模型需要改進。

3. 指令時間

由於大多數計算機系統都會使用快取技術，所以每條執行所需的時間並不是總是相同。

4. 系統因素

如果計算機同時執行很多程式，會產生爭奪資源的情況，這會影響實驗結果。

5. 對輸入的強烈依賴

在研究程式的執行時間的增長數量級時，我假設執行時間和輸入相對無關。當這個條件不滿足時，會得到不一致或者錯誤的結果。例如，ThreeSum 返回的不是三個整數為0的對數，而是是否存在。如果前三個整數就滿足，該程式的執行時間的增長數量級為常數；如果輸入不含有這樣的三個整數，程式的執行時間的增長量級為立方級別。

6. 多個問題參量

ThreeSum 效能分析是僅需要一個參量的函數來衡量程式的效能，參量一般是輸入的規模。但是，多個參量也是有可能的。例如白名單（一個整數列表 M 個，一個白名單整數列表 N個，返回整數列表中有多少個整數在白名單中存在）,執行時間一般和 M logN 成正比。

6. 處理對於輸入的依賴

輸入模型：我們可以仔細模擬要處理的輸入的種類。這種方法具有挑戰性，因為該模型可能是不現實的。

最壞情況下的效能保證：不管輸入什麼，程式的執行時間都小於一定的範圍（取決於輸入大小）。這種保守的方法可能適用於執行核反應堆或心臟起搏器或汽車制動器的軟體。

隨機演演算法：提供效能保證的一種方法是引入隨機性，例如快速排序和雜湊。每次您執行演演算法時，都會花費不同的時間。這些保證不是絕對的，但是它們無效的機會小於您的計算機被閃電擊中的機會。因此，這種保證在實踐中與最壞情況的保證一樣有用。

操作序列：對於許多應用程式，演演算法輸入可能不僅是資料，還包括使用者端執行的操作順序。

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

7.記憶體

計算程式對記憶體的使用情況和執行時間一樣重要。計算機中電路的很大一部分作用就是幫助應用程式儲存一些值並在使用時取出。儲存的值越多，需要的電路越多，需要的記憶體也越多。

.net 記憶體分配系統已經幫我們解決了記憶體問題。

.net 使用 8 位（64位元）表示位元組，每個基本型別需要的記憶體：

1. 物件

一個物件所使用的記憶體，需要將所有範例變數使用記憶體與物件本身的開銷（一般是16位元組，這些開銷包括一個指向物件的類的參照，垃圾回收資訊和同步資訊）以及4個填充位元組相加。

當我們說一個參照所佔的記憶體時，指的是它所指向的物件所佔的記憶體。物件的參照通常是一個記憶體地址，因此使用8個位元組的記憶體（在64位元計算機上）。

2. 連結串列

巢狀的非靜態類需要額外的8位元組。例如，如果 Node 類是巢狀類，基於連結串列的棧中一個Node物件需要 40 位元組（16位元組的物件開銷，兩個物件參照各需8位元組，還有8位元組的額外開銷。為什麼不需要填充位元組）。

因為一個 Integer 物件需要24位元組，所以一個含有 N 個整數的基於連結串列的表需要 32 + 64 N 位元組（Stack 物件開銷 16 位元組，參照型別範例變數 8 位元組，int 型別範例變數 4 位元組，4個填充位元組，每個元素64位元組（一個 Node 物件40位元組和一個Integer 物件 24 位元組））

3. 陣列

C# 中陣列是參照型別，一般都會因為記錄長度需要額外的記憶體。一個基礎型別的陣列一般需要24位元組的頭資訊（16位元組的物件開銷，4位元組用於儲存長度以及4填充位元組）再加上儲存值所需的記憶體。例如一個含有 N個 int 值的陣列需要 24 + 4N (會被填充為 8 的倍數)

4. 字串物件

String 的標準實現含有4個範例變數：一個指向字元陣列的參照（8位元組）和三個 int 值（各4位元組）。第一個 int 值描述的是字元陣列中的偏移量，第二個 int 值是字串的長度。第三個值是一個雜湊值，它在某些情況下可以節省計算。總共需要40位元組，這是除字元陣列之外字串所需的記憶體空間，加上字元陣列的話是 40 + 24 + 2N = 64 + 2N。

但是，字元陣列常常是在多個字串之間共用的。因為 String 物件是不可變的，這種設計使 String 的實現能夠在多個String物件中都含有相同的字元陣列時節省記憶體。

當使用 SubString 建立了一個新的 String 物件（40位元組），但它仍重用了相同的字元陣列。

當涉及到函數呼叫時，記憶體的消耗是一個複雜的動態過程。當呼叫一個方法時，系統會從記憶體中的一個特定區域為方法分配所需的記憶體（用於儲存區域性變數），這個區域叫做棧。當方法返回時，佔用的記憶體將被返回給棧，所以，在遞迴呼叫中不要建立大型的物件。當使用 new 建立物件時，系統會在堆中分配所需的記憶體，而且物件會一直存在，知道沒有任何對它的參照。

到此這篇關於C#演演算法設計與分析的文章就介紹到這了。希望對大家的學習有所幫助，也希望大家多多支援it145.com。