Delphi 提供了豐富的內建資料結構，例如 TStringList、TList、TDictionary 等，方便開發者存取和管理資料。然而，不同資料結構的操作效能差異顯著，理解其時間複雜度對於提升程式效能至關重要。TStringList 在未排序狀態下，新增元素速度很快，但查詢操作需要遍歷整個列表，時間複雜度為 O(n)。排序後的 TStringList 則可利用二分搜尋，將查詢操作的時間複雜度降至 O(log n)。TDictionary 則利用雜湊表實作，平均情況下，新增、刪除和查詢操作的時間複雜度都接近 O(1)，但在極端情況下，例如雜湊碰撞嚴重時，效能可能會退化到 O(n)。選擇合適的資料結構需要根據具體應用場景的需求，例如，若頻繁進行查詢操作，TDictionary 通常是更優的選擇；若需要保持元素的順序，則 TStringList 更為適用。
演算法複雜度
在探討程式效能時，我們會遇到兩種型別的效能問題：
- 對使用者輸入反應迅速的程式
- 能夠快速進行計算的程式
正如我們將會看到的，實作前者和後者的技術是不同的。要讓程式反應迅速，有時只需將長時間執行的操作（如虛擬遊戲中計算下一步）放入背景執行緒中即可。程式碼仍會執行與原始版本相同的操作，但使用者介面不會被阻塞，這樣大家都會很滿意。
為了加快程式的執行速度（這也有助於改善反應遲緩的使用者介面），我們可以使用不同的技術，從改變演算法到修改程式碼使其同時使用多個 CPU，乃至使用手動最佳化的版本，無論是由我們自己撰寫還是從外部函式庫匯入。
要進行任何改進，我們必須知道程式碼的哪一部分造成了問題。如果我們正在處理一個龐大的舊式程式，問題部分可能很難找到。在本章的其餘部分，我們將探討不同的方法來定位這類別程式碼。我們將從有根據的猜測開始，然後透過測量程式碼速度來改進它，首先使用自製工具，然後使用一些不同的開源和商業程式。
大O符號
在開始進行改程式式速度的「骯髒」（且有趣）工作之前，我想先介紹一點電腦科學理論，即大O符號。
您不必擔心，我不會使用大量的數學公式，也不會談論無窮小漸近線。相反，我將介紹大O符號的精髓，即每個程式設計師都應該瞭解的部分。
在文獻和網路上，您會看到諸如 O(n)、O(n^2)、O(1) 等表示式。這種看似高深的符號背後其實有個簡單的故事。它告訴我們，如果將資料大小增加 n 倍，演算法會變慢多少。
資訊
n^2 符號表示「n 的二次方」，即 n 的平方。這種符號在網際網路上很常見，因為它可以用標準的 ASCII 字元表示。本文使用更易讀的形式 O(n^2)。
假設我們有一個複雜度為 O(n) 的演算法，平均需要 T 秒來處理大小為 N 的輸入資料。如果我們將資料大小增加 10 倍（達到 10N），則該演算法平均也需要 10 倍的時間（即 10T）來處理資料。如果我們處理的資料量是原來的 1,000 倍，則程式的執行速度也會慢 1,000 倍。
如果演算法複雜度為 O(n^2)，將資料大小增加 10 倍將導致演算法執行時間增加 10^2 或 100 倍。如果我們要處理的資料量是原來的 1,000 倍，則該演算法將需要 1,000^2 或一百萬倍的時間，這是一個相當大的影響。這類別演算法在處理大量資料時通常不是很有用。
注意
大多數情況下，我們使用大O符號來描述計算時間與輸入資料大小之間的關係。在這種情況下，我們稱大O符號為時間複雜度。另一方面，有時相同的符號用於描述演算法使用的儲存空間（記憶體）。在這種情況下，我們談論的是空間複雜度。
您可能已經注意到，我在前幾段中多次使用了「平均」這個詞。在討論演算法複雜度時，我們主要關注的是平均行為，但有時我們也需要了解最壞情況下的行為。我們很少談論最佳行為，因為使用者並不在乎程式是否偶爾比平均速度快。
讓我們看一個例子。以下函式檢查字串引數值是否存在於字串清單中：
function IsPresentInList(strings: TStrings; const value: string): Boolean;
var
i: Integer;
begin
Result := False;
for i := 0 to strings.Count - 1 do
if SameText(strings[i], value) then
Exit(True);
end;
內容解密：
此函式遍歷 strings 清單中的每個元素，並檢查是否與 value 相等。如果找到匹配項，則立即傳回 True。如果遍歷完所有元素仍未找到匹配項，則傳回 False。
for i := 0 to strings.Count - 1 do：遍歷清單中的每個字串。if SameText(strings[i], value) then：比較當前字串與目標值是否相等（不區分大小寫）。Exit(True)：如果找到匹配項，立即離開函式並傳回True。- 如果迴圈結束仍未找到匹配項，則傳回
False。
對於這個函式，我們可以說什麼？最佳情況非常簡單——它會發現 value 等於 strings[0]，然後離開。太好了！我們的函式的最佳行為是 O(1)。但遺憾的是，這並不能告訴我們太多，因為這種情況在實際中並不常見。
最壞情況也很容易找到。如果 value 不在清單中，程式碼將不得不掃描整個 strings 清單，才能決定應該傳回 False。換句話說，最壞情況下的行為是 O(n)，其中 n 代表清單中的元素數量。同樣明顯（且簡單證明）的是，平均而言，該演算法在 n/2 步中找到一個元素。那麼，這種搜尋的大O限制是否為 O(n/2)？
注意
大O限制不關心常數因子。如果一個演算法平均使用 n/2 步，甚至只是 0.0001 * n 步，我們仍然會將其寫為 O(n)。當然，一個 O(10 * n) 的演算法比 O(n) 的演算法慢，這在我們微調程式碼時非常重要，但沒有任何常數因子 C 能使 O(C * n) 比 O(log n) 快，如果 n 足夠大。
還有比順序搜尋清單更好的方法來檢查元素是否存在於某些資料中。我們將在下一節中探討其中一種方法，大O符號與 Delphi 資料結構。
雖然 O() 符號內的 n 的函式可以是任意的，但有一些 O 函式在標準程式設計問題中經常出現。下表顯示了這些常見的大O限制以及屬於每類別問題的最常見範例：
| 時間複雜度 | 常見問題範例 |
|---|---|
| O(1) | 存取陣列元素 |
| O(log n) | 在有序清單中搜尋 |
| O(n) | 線性搜尋 |
| O(n log n) | 快速排序（平均行為） |
| O(n^2) | 快速排序（最壞情況）、樸素排序（氣泡排序、插入排序、選擇排序） |
| O(c^n) | 遞迴斐波那契數列、使用動態規劃解決旅行商問題（c 是某個數值常數） |
如果我們關心程式效能，那麼 O(1) 的演算法對我們來說特別重要，因為它們代表了不會隨著問題規模增加而變慢（至少不明顯變慢）的演算法。我們將在下一節中看到這種 O(1) 演算法的範例。
當我們處理在某些資料集中搜尋的演算法時，我們通常會嘗試使其表現為 O(log n)，而不是 O(n)，因為前者比後者慢得更不明顯。
另一大類別問題涉及對資料進行排序。雖然樸素方法以 O(n^2) 的時間複雜度進行排序，但更好的演算法（如合併排序和快速排序）平均只需要 O(n log n) 步。
下圖顯示了這些典型限制的時間複雜度（我們使用 2^n 作為更通用的 c^n 的範例）在問題規模增加至 20 倍時的增長情況：
常見大O限制的增長比較
@startuml
skinparam backgroundColor #FEFEFE
skinparam defaultTextAlignment center
skinparam rectangleBackgroundColor #F5F5F5
skinparam rectangleBorderColor #333333
skinparam arrowColor #333333
title 常見大O限制的增長比較
rectangle "1" as node1
rectangle "10" as node2
rectangle "90" as node3
rectangle "900" as node4
rectangle "急劇增加" as node5
node1 --> node2
node2 --> node3
node3 --> node4
node4 --> node5
@enduml圖表翻譯： 此圖表顯示了不同大O時間複雜度在資料規模增加時的增長情況。其中，O(1) 和 O(log n) 的增長非常緩慢，而 O(n log n) 和 O(n^2) 的增長較快，尤其是當資料規模進一步擴大時，O(2^n) 的增長最為劇烈。
我們可以看到，O(1) 和 O(log n) 的增長非常緩慢。雖然 O(n log n) 的增長比 O(n) 快，但仍然比 O(n^2) 慢得多，而當資料增加九倍時，我們不得不停止繪製 O(n^2)。O(2^n) 一開始增長緩慢，看起來對於小資料量（小 n）是一個很好的解決方案，但隨後開始急劇上升，遠遠快於 O(n^2)。
下表顯示了與 O(n) 相比，O(n log n) 和 O(n^2) 的增長速度有多快，以及 O(2^n) 的爆炸性增長。
表格：不同時間複雜度的增長比較
| 資料規模 | O(n) | O(n log n) | O(n^2) | O(2^n) |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 2 |
| 10 | 10 | 33 | 100 | 1024 |
| … | … | … | … | … |
內容解密：
此表格顯示了不同時間複雜度的演算法在處理不同規模資料時的相對效能。可以看出，隨著資料規模的增加，O(n^2) 和 O(2^n) 的執行時間迅速增加，而 O(n log n) 的增長相對較慢。
演算法複雜度與Delphi資料結構效能分析
在探討軟體開發中的效能最佳化時，演算法複雜度（Big-O notation）扮演著至關重要的角色。本篇文章將深入分析不同演算法複雜度對程式效能的影響，並著重介紹Delphi中常見的資料結構及其操作的時間複雜度。
演算法複雜度比較
| 資料量 | O(1) | O(log n) | O(n) | O(n log n) | O(n^2) | O(2^n) | |
-|
-|
|
-|
-|
|
| | 1 | 1 | 1 | 1 | 1 | 1 | 1 | | 2 | 1 | 2 | 2 | 4 | 4 | 2 | | 10 | 1 | 4 | 10 | 43 | 100 | 512 | | 20 | 1 | 5 | 20 | 106 | 400 | 524,288 | | 100 | 1 | 8 | 100 | 764 | 10,000 | 超過10^29 | | 300 | 1 | 9 | 300 | 2,769 | 90,000 | 超過10^90 |
從上述表格中，我們可以明顯看出不同演算法複雜度在處理不同資料量時的效能差異。尤其是當資料量增大時，O(log n)和O(n log n)的演算法相比於O(n)和O(n^2)顯示出明顯的優勢，而O(2^n)的演算法則迅速變得不可管理。
重點解析
- O(log n)的演算法在資料量增加時，效能遠優於O(n)的演算法。
- O(2^n)的演算法在資料量稍有增加時，便會面臨效能災難。
Delphi中的資料結構與其時間複雜度
Delphi的執行期函式庫（RTL）提供了多種資料結構，幫助開發者高效地儲存和檢索資料。然而，每種資料結構都有其優缺點，開發者需要根據具體需求進行選擇。
TStringList的效能特點
TStringList是Delphi中最常用的資料結構之一，它支援未排序和排序兩種模式。
- 未排序模式：新增元素（Add）操作為O(1)，但查詢（IndexOf）操作需要O(n)的時間複雜度。
- 排序模式：新增元素需要O(log n)的時間複雜度來找到正確的插入位置，查詢操作同樣為O(log n)。
其他資料結構
- TList和TObjectList：這兩種資料結構總是以未排序模式運作，新增元素為O(1)，但查詢和刪除元素需要O(n)的時間複雜度。
- TList
和TObjectList ：除了具備TList和TObjectList的功能外，還提供了BinarySearch方法，能夠以O(log n)的時間複雜度進行二分查詢，但前提是列表必須已排序。 - TDictionary：提供了快速的新增、刪除和查詢操作，平均時間複雜度為O(1)。然而，它不能直接存取元素，且不保持元素的新增順序。
- TQueue
和TStack ：這兩種資料結構分別實作了佇列和堆積疊的功能，提供O(1)的新增和刪除操作，並且能夠直接存取內部陣列。
重點建議
在選擇資料結構時，應根據實際需求進行權衡。例如，若需要快速的元素查詢，則TDictionary可能是最佳選擇；若需要保持元素的順序，則TList或TStringList的排序模式可能更合適。
程式碼範例：使用TDictionary進行快速查詢
var
Dict: TDictionary<string, Integer>;
begin
Dict := TDictionary<string, Integer>.Create;
try
// 新增元素
Dict.Add('key1', 1);
Dict.Add('key2', 2);
// 快速查詢
if Dict.ContainsKey('key1') then
ShowMessage('Value: ' + Dict['key1'].ToString);
finally
Dict.Free;
end;
end.
程式碼解析
此範例展示瞭如何使用TDictionary進行元素的快速新增和查詢。TDictionary的ContainsKey方法用於檢查鍵是否存在，而透過鍵可以直接存取對應的值。
效能探討：內建 Delphi 資料結構的時間複雜度分析
在軟體開發中，資料結構的選擇對於程式的效能有著舉足輕重的影響。本文將探討 Delphi 中常見的內建資料結構的時間複雜度，並透過一個實際的範例專案 RandomWordSearch 來展示不同資料結構在實際應用中的效能差異。
常見內建 Delphi 資料結構的時間複雜度
| 資料結構 | 操作 | 平均時間複雜度 | 最壞時間複雜度 |
|---|---|---|---|
TList<T>, TObjectList<T> | 直接存取 | O(1) | |
| 新增 | O(1) | ||
| 插入 | O(1) | ||
| 刪除 | O(1) | ||
| 移除 | O(n) | ||
IndexOf | O(n) | ||
BinarySearch | O(log n) | ||
| 排序 | O(n log n) | O(n^2) | |
TDictionary | 直接存取 | 不可能 | |
| 新增 | O(1) | O(n) | |
| 移除 | O(1) | O(n) | |
TryGetValue | O(1) | O(n) | |
ContainsKey | O(1) | O(n) | |
ContainsValue | O(n) | ||
TQueue<T> | 直接存取 | 不可能 | |
| 入佇列 | O(1) | ||
| 出佇列 | O(1) | ||
TStack<T> | 直接存取 | 不可能 | |
| 推入堆積疊 | O(1) | ||
| 彈出堆積疊 | O(1) |
表格解說：
此表格列出了 Delphi 中常見的內建資料結構及其操作對應的時間複雜度。其中，TList<T> 和 TObjectList<T> 提供快速的直接存取、新增、插入和刪除操作，但 IndexOf 操作的時間複雜度為 O(n)。TDictionary 提供快速的鍵值對查詢，但當發生雜湊碰撞時，最壞情況下的時間複雜度會退化為 O(n)。TQueue<T> 和 TStack<T> 分別提供先進先出和後進先出的操作，且入佇列、出佇列、推入堆積疊和彈出堆積疊的操作時間複雜度均為 O(1)。
RandomWordSearch 範例專案分析
RandomWordSearch 專案的功能是隨機生成英文單字，並檢查生成的單字是否存在於預先載入的單字列表中。該專案使用了三種不同的資料結構來儲存單字列表：未排序的 TStringList、排序的 TStringList 和 TDictionary。
程式碼實作：
procedure TfrmRandomWordSearch.LoadWords(wordList: TStringList);
var
word: string;
begin
FWordsUnsorted := TStringList.Create;
FWordsUnsorted.Assign(wordList);
FWordsSorted := TStringList.Create;
FWordsSorted.Assign(wordList);
FWordsSorted.Sorted := True;
FWordsDictionary := TDictionary<string, boolean>.Create(wordList.Count);
for word in wordList do
FWordsDictionary.Add(word, True);
end;
程式碼解密：
在上述程式碼中，我們首先載入單字列表到三個不同的資料結構中。未排序的 TStringList (FWordsUnsorted) 直接複製了單字列表。排序的 TStringList (FWordsSorted) 在複製單字列表後，將其排序。TDictionary (FWordsDictionary) 以單字作為鍵，布林值作為值，儲存了單字列表。這裡使用布林值只是為了滿足 TDictionary 需要鍵值對的要求，實際上我們只關心鍵的部分。
按鈕點選事件處理
當點選不同的按鈕時，程式會呼叫 FindGoodWord 方法，並傳入不同的測試函式來檢查生成的隨機單字是否存在於對應的資料結構中。
procedure TfrmRandomWordSearch.btnUnsortedListClick(Sender: TObject);
begin
FindGoodWord(
function(const word: string): boolean
begin
Result := FWordsUnsorted.IndexOf(word) >= 0;
end);
end;
procedure TfrmRandomWordSearch.btnSortedListClick(Sender: TObject);
begin
FindGoodWord(
function(const word: string): boolean
begin
Result := FWordsSorted.IndexOf(word) >= 0;
end);
end;
程式碼解密：
在上述程式碼中，btnUnsortedListClick 和 btnSortedListClick 事件處理函式分別呼叫了 FindGoodWord 方法，並傳入了不同的測試函式。對於未排序的 TStringList，測試函式使用 IndexOf 方法來檢查單字是否存在，這需要遍歷整個列表，時間複雜度為 O(n)。對於排序的 TStringList，IndexOf 方法會使用二分搜尋，時間複雜度為 O(log n)，顯著提高了查詢效率。
