演算法複雜度與程式碼效能分析

程式效能是軟體開發的關鍵指標，而演算法的選擇直接影響程式執行效率。不同的演算法複雜度會導致程式在處理大量資料時效能差異巨大。以字串查詢為例，未排序列表的線性搜尋時間複雜度為 O(n)，排序列表的二分搜尋則為 O(log n)，而字典的查詢則能達到 O(1)。在 SlowCode 範例中，核心函式 SlowMethod 和 Filter 函式都包含巢狀迴圈，導致整體時間複雜度達到 O(n^2)，效能瓶頸明顯。實際測量結果也驗證了時間複雜度的分析，隨著輸入資料量的增加，執行時間呈現平方級增長。

效能探討：演算法複雜度的重要性

在軟體開發領域，效能始終是開發者關注的重點之一。當程式執行速度不盡人意時，首先需要檢查的是所使用的演算法是否足夠高效。本文將透過例項探討不同演算法複雜度對程式效能的影響，並介紹如何找出程式中的效能瓶頸。

不同演算法複雜度的比較

在前面的章節中，我們探討了三種不同的演算法，分別用於檢查一個單字是否存在於一個單字列表中：

1. 未排序列表：使用 TStringList 儲存單字，並透過遍歷列表來檢查單字是否存在，時間複雜度為 O(n)。
2. 排序列表：同樣使用 TStringList，但在加入單字時保持列表排序，利用二分搜尋法檢查單字是否存在，時間複雜度為 O(log n)。
3. 字典：使用 TDictionary 儲存單字，直接利用字典的快速查詢特性，時間複雜度為 O(1)。

程式碼實作

以下是三種演算法的程式碼範例：

// 未排序列表
procedure TfrmRandomWordSearch.btnUnsortedClick(Sender: TObject);
begin
  FindGoodWord(
    function (const word: string): boolean
    begin
      Result := FWordsUnsorted.IndexOf(word) >= 0;
    end);
end;

// 排序列表
procedure TfrmRandomWordSearch.btnSortedClick(Sender: TObject);
begin
  FindGoodWord(
    function (const word: string): boolean
    begin
      Result := FWordsSorted.IndexOf(word) >= 0;
    end);
end;

// 字典
procedure TfrmRandomWordSearch.btnDictionaryClick(Sender: TObject);
begin
  FindGoodWord(
    function (const word: string): boolean
    begin
      Result := FWordsDictionary.ContainsKey(word);
    end);
end;

效能比較

實驗結果表明，當單字長度增加時，未排序列表的查詢時間急劇上升，而排序列表和字典的查詢時間相對穩定。尤其是字典，由於其 O(1) 的時間複雜度，表現出遠超其他兩種演算法的效能。

Mr. Smith 的 SlowCode 程式

接下來，我們將分析 Mr. Smith 編寫的 SlowCode 程式，以瞭解其效能瓶頸所在。

程式功能

SlowCode 程式是一個控制檯應用程式，主要功能是根據使用者輸入的數字，生成一個整數列表，並對列表中的數字進行篩選。

程式碼分析

SlowCode 程式的核心函式是 SlowMethod，它負責生成整數列表並進行篩選。篩選條件是檢查數字是否能被列表中的其他數字整除。

function SlowMethod(highBound: Integer): TArray<Integer>;
var
  i: Integer;
  temp: TList<Integer>;
begin
  temp := TList<Integer>.Create;
  try
    for i := 2 to highBound do
      if not ElementInDataDivides(temp, i) then
        temp.Add(i);
    Result := Filter(temp);
  finally
    FreeAndNil(temp);
  end;
end;

function ElementInDataDivides(data: TList<Integer>; value: Integer): boolean;
var
  i: Integer;
begin
  Result := True;
  for i in data do
    if (value <> i) and ((value mod i) = 0) then
      Exit;
  Result := False;
end;

function Filter(list: TList<Integer>): TArray<Integer>;
var
  i: Integer;
  reversed: Integer;
begin
  SetLength(Result, 0);
  for i in list do
  begin
    reversed := StrToInt(Reverse(IntToStr(i)));
    if not ElementInDataDivides(list, reversed) then
    begin
      SetLength(Result, Length(Result) + 1);
      Result[High(Result)] := i;
    end;
  end;
end;

#### 內容解密：

• SlowMethod函式建立了一個整數列表，並遍歷從2到使用者輸入的值，將不被列表中現有數字整除的數字加入列表。
• ElementInDataDivides函式檢查給定的值是否能被列表中的任何數字整除，若能，則傳回True。
• Filter函式對列表中的每個數字進行反轉，並再次呼叫ElementInDataDivides檢查反轉後的數字是否能被列表中的其他數字整除，若不能，則將原數字加入結果陣列。

效能分析與改進：從Big O到程式碼最佳化

在探討程式效能的過程中，Big O符號提供了一個評估程式時間與空間複雜度的有效工具。本文將透過一個具體的範例，分析程式碼的效能瓶頸，並提出改進方案。

程式碼分析

首先，觀察給定的程式碼片段：

for i := 2 to highBound do
  if not ElementInDataDivides(temp, i) then
    temp.Add(i);

這個迴圈的時間複雜度為O(n)，其中n等於highBound。在迴圈內部，ElementInDataDivides函式被呼叫，其本身也包含一個O(n)的迴圈。因此，整體時間複雜度為O(n^2)。

ElementInDataDivides函式分析

for i in data do
  if (value <> i) and ((value mod i) = 0) then
    Exit;

這個函式檢查value是否能被data中的任何元素整除。同樣具有O(n)的時間複雜度。

Filter函式分析

for i in list do
begin
  reversed := StrToInt(Reverse(IntToStr(i)));
  if not ElementInDataDivides(list, reversed) then
  begin
    SetLength(Result, Length(Result) + 1);
    Result[High(Result)] := i;
  end;
end;

這個函式遍歷list，對每個元素進行反轉並檢查是否符合條件。整體時間複雜度同樣為O(n^2)，因為它呼叫了ElementInDataDivides。

#### 內容解密：

• for i := 2 to highBound do：這個迴圈從2迭代到使用者指定的上限，檢查每個數字是否為質數。
• ElementInDataDivides：檢查給定的值是否能被資料列表中的任何元素整除，若能，則傳回True。
• Filter函式：對輸入列表中的每個數字進行反轉，並檢查反轉後的數字是否符合條件。

時間複雜度分析

綜合上述分析，該程式的主要效能瓶頸在於：

1. SlowMethod中的雙重O(n)迴圈導致O(n^2)的時間複雜度。
2. Filter函式同樣具有O(n^2)的時間複雜度。

#### 內容解密：

• 程式的主要耗時部分在於ElementInDataDivides函式和Filter函式中的迴圈操作。
• 使用SetLength動態調整陣列大小也可能帶來額外的效能開銷。

改進建議

1. 最佳化ElementInDataDivides函式：可以考慮使用更高效的演算法來檢查質數，例如使用篩法（Sieve of Eratosthenes）預先計算質數列表。

   procedure SieveOfEratosthenes(n: Integer; var primes: TList<Integer>);
   var
     i, j: Integer;
     prime: array of Boolean;
   begin
     SetLength(prime, n + 1);
     for i := 0 to n do
       prime[i] := True;
     prime[0] := False;
     prime[1] := False;
     for i := 2 to Trunc(Sqrt(n)) do
       if prime[i] then
         for j := i * i to n do += i do
           prime[j] := False;
     for i := 2 to n do
       if prime[i] then
         primes.Add(i);
   end;
   

   #### 內容解密：

   • SieveOfEratosthenes函式用於生成質數列表。
   • 初始化一個布林陣列prime來標記數字是否為質數。
   • 從2開始，標記所有其倍數為非質數。

2. 使用TList<T>替代動態陣列：在Filter函式中，使用TList<Integer>來暫存結果，最後再轉換為陣列，可以避免頻繁的SetLength呼叫。

   var
     resultList: TList<Integer>;
   begin
     resultList := TList<Integer>.Create;
     try
       for i in list do
       begin
         reversed := StrToInt(Reverse(IntToStr(i)));
         if not ElementInDataDivides(list, reversed) then
           resultList.Add(i);
       end;
       Result := resultList.ToArray;
     finally
       resultList.Free;
     end;
   end;
   

   #### 內容解密：

   • 使用TList<Integer>來動態儲存結果，避免了頻繁的記憶體重新分配。
   • 最後將TList<Integer>轉換為陣列傳回。

程式碼效能分析

「不要猜測，要測量！」這句話在程式碼最佳化中非常重要。要了解程式的效能瓶頸，唯一的方法是測量它。我們可以手動在程式碼中插入計時程式碼，也可以利用專業的工具來進行測量。測量的過程被稱為效能分析，而用於測量的工具則被稱為效能分析器。

在本章中，我們將探討不同的測量執行速度的技術。首先，我們會使用一個簡單的軟體秒錶來測量熟悉的 SlowCode 程式，然後介紹一些開源和商業的效能分析器。

效能分析的基本規則

在開始之前，有幾條基本規則需要遵守：

• 絕對不要在偵錯模式下進行效能分析，因為偵錯模式會使程式在某些地方執行得更慢，從而影響測量結果。
• 在進行效能分析時，盡量不要在電腦上執行其他程式，因為其他程式會佔用 CPU 資源，使被測量的程式執行得更慢。
• 確保程式不會在效能分析過程中等待使用者輸入，這會嚴重影響測量結果。
• 重複執行測試多次，因為 Windows（以及 Delphi 支援的其他作業系統）總是在執行其他任務，這會導致每次執行的時間不同。
• 這些規則對於多執行緒程式尤其重要。

使用 TStopwatch 進行效能分析

Delphi 提供了一個名為 System.Diagnostics 的單元，其中實作了一個 TStopwatch 記錄型別。它允許我們以高於 1 毫秒的精確度測量時間事件。以下是 TStopwatch 的部分公開介面：

type
  TStopwatch = record
  public
    class function Create: TStopwatch; static;
    class function GetTimeStamp: Int64; static;
    procedure Reset;
    procedure Start;
    class function StartNew: TStopwatch; static;
    procedure Stop;
    property Elapsed: TTimeSpan read GetElapsed;
    property ElapsedMilliseconds: Int64 read GetElapsedMilliseconds;
    property ElapsedTicks: Int64 read GetElapsedTicks;
    class property Frequency: Int64 read FFrequency;
    class property IsHighResolution: Boolean read FIsHighResolution;
    property IsRunning: Boolean read FRunning;
  end;

要使用 TStopwatch，首先需要建立它。可以呼叫 TStopwatch.Create 建立一個新的停止的秒錶，或呼叫 TStopwatch.StartNew 建立一個新的啟動的秒錶。由於 TStopwatch 是以記錄型別實作的，因此不需要銷毀秒錶物件。

使用 TStopwatch 測量 SlowMethod

首先，需要在 uses 清單中加入 System.Diagnostics 單元：

uses
  System.SysUtils,
  System.Generics.Collections,
  System.Classes,
  System.Diagnostics;

然後，在 SlowMethod 中建立一個 TStopwatch，在結束時停止它，並輸出經過的時間：

function SlowMethod(highBound: Integer): TArray<Integer>;
var
  // existing variables
  sw: TStopwatch;
begin
  sw := TStopwatch.StartNew;
  // existing code
  sw.Stop;
  Writeln('SlowMethod: ', sw.ElapsedMilliseconds, ' ms');
end;

驗證時間複雜度

透過測量不同輸入值的執行時間，可以驗證 SlowCode 的時間複雜度是否為 O(n^2)。以下是測量的結果：

透過在 Excel 中繪製散點圖，並新增冪趨勢線，可以看到擬合函式接近 x^2。同樣，在 Wolfram Alpha 中使用迴歸計算器小工具，也得到了類別似的結果：4.76372×10^-8 * x^2 + 0.0064733 * x - 143.666。忽略常數項和次要因素後，主要部分仍然是 x^2。

詳細測量

雖然我們已經瞭解了 SlowCode 的整體行為，但仍然不知道哪部分程式碼最慢。為了找到答案，需要測量 ElementInDataDivides 和 Filter 方法的執行時間。

由於這兩個方法被多次呼叫，因此不能簡單地每次建立和銷毀一個 TStopwatch。需要建立全域的 TStopwatch，這在 SlowCode_Stopwatch 程式中已經實作：

var
  Timing_ElementInData: TStopwatch;
  Timing_Filter: TStopwatch;
  Timing_SlowMethod: TStopwatch;

程式碼解密：

• 在上述範例中，我們使用了 TStopwatch來測量函式的執行時間。
• 首先，我們需要在 uses 子句中加入 System.Diagnostics，以便使用 TStopwatch。
• 接著，在要測量的函式中建立一個 TStopwatch物件，並在函式開始時啟動它，在結束時停止它。
• 最後，我們輸出經過的時間，以瞭解函式的執行效率。

圖表翻譯：

此圖示展示了測量結果與擬合曲線之間的關係，驗證了 SlowCode的時間複雜度確實接近 O(n^2)。左側為 Excel 中的曲線擬合結果，右側為 Wolfram Alpha 的迴歸分析結果。兩者都顯示出 x^2 的主要趨勢。