Spring4D 字典與集合深入解析及效能最佳化技巧

– 13 分鐘閱讀

Spring4D 提供了豐富的字典和集合型別，方便開發者處理資料。IDictionary 介面定義了鍵值對的存取方式，底層實作可以是雜湊表或紅黑樹，影響著存取效能。雙向字典允許透過鍵或值進行查詢，多重對映則允許一個鍵對應多個值，並提供不同實作方式，例如 MultiMap、HashMultiMap、TreeMultiMap 等，各有其效能特性。理解這些差異有助於選擇合適的資料結構。除了資料結構的選擇，Delphi 編譯器設定也會影響程式效能。記錄欄位對齊設定 ($ALIGN) 會影響記憶體佈局和存取效率，範圍檢查設定 ($R) 則會影響執行速度，需要在效能和安全性之間取得平衡。開發者可以根據實際情況調整這些設定，例如在發布版本中關閉部分範圍檢查以提升效能。

字典介面

字典是一個自然的集合擴充套件，儲存著關聯的鍵和值。字典可以儲存一個特定的鍵只一次。Spring的字典介面IDictionary<TKey, TValue>與Delphi版本相似，提供了新增、刪除、查詢和更新鍵值對的方法。

字典的存取和複雜度

字典的存取和複雜度取決於其實作。未排序的字典使用雜湊表實作，具有更好的時間複雜度，而排序的字典使用紅黑樹實作。未排序的字典的存取時間為O(1)，而排序的字典的存取時間為O(log n)。

雙向字典

雙向字典是一種字典，可以使用鍵查詢值，也可以使用值查詢鍵。雙向字典由兩個相互連線的字典實作，一個對映鍵到值，另一個對映值到鍵。雙向字典的存取時間為O(1)。

實作和複雜度

字典和集合的實作和複雜度取決於其底層資料結構。未排序的字典和集合使用雜湊表實作，具有更好的時間複雜度，而排序的字典和集合使用紅黑樹實作。未排序的字典和集合的存取時間為O(1)，而排序的字典和集合的存取時間為O(log n)。

範例程式碼

以下是使用Spring的字典介面IDictionary<TKey, TValue>的範例程式碼：

from spring import IDictionary

# 建立一個字典
dict = IDictionary[str, int]()

# 新增鍵值對
dict.Add("apple", 1)
dict.Add("banana", 2)

# 查詢鍵的值
print(dict["apple"])  # 輸出: 1

# 更新鍵的值
dict["apple"] = 3
print(dict["apple"])  # 輸出: 3

# 刪除鍵值對
dict.Remove("banana")

# 查詢鍵是否存在
print("apple" in dict)  # 輸出: True
print("banana" in dict)  # 輸出: False

這個範例程式碼示範瞭如何使用Spring的字典介面IDictionary<TKey, TValue>新增、查詢、更新和刪除鍵值對。

多重對映（Multimap）介紹

多重對映（Multimap）是一種複雜的集合型別，它允許每個鍵與多個值相關聯。這種集合型別由 IMultiMap<TKey, TValue> 介面定義，該介面繼承自 IMap<TKey, TValue> 介面。

多重對映介面

IMultiMap<TKey, TValue> 介面提供了多種方法和屬性，包括：

  • Add(const key: TKey; const value: TValue): Boolean;：新增一個鍵值對到多重對映中。
  • AddRange(const key: TKey; const values: array of TValue);：新增多個值到多重對映中，與同一個鍵相關聯。
  • Extract(const key: TKey): ICollection<TValue>;：從多重對映中提取所有與指定鍵相關聯的值。
  • TryGetValues(const key: TKey; var values: IReadOnlyCollection<TValue>): Boolean;：嘗試從多重對映中取得所有與指定鍵相關聯的值。
  • AsReadOnly: IReadOnlyMultiMap<TKey, TValue>;：取得多重對映的唯讀版本。
  • Items[const key: TKey]: IReadOnlyCollection<TValue> read GetItems; default;：取得所有與指定鍵相關聯的值。

多重對映的複雜性

多重對映的複雜性來自於其實作細節。多重對映可以是無序的（根據雜湊表）或有序的（根據紅黑樹）。此外，多重對映可以支援多個值、唯一值、有序值或無序值。這些不同的組合反映在 TCollections 工廠中。

多重對映工廠

TCollections 工廠提供了多種多重對映工廠，包括：

  • CreateMultiMap<TKey, TValue>(ownerships: TDictionaryOwnerships = []): IMultiMap<TKey, TValue>;：建立一個多重對映。
  • CreateHashMultiMap<TKey, TValue>(ownerships: TDictionaryOwnerships = []): IMultiMap<TKey, TValue>;：建立一個根據雜湊表的多重對映。
  • CreateTreeMultiMap<TKey, TValue>(ownerships: TDictionaryOwnerships = []): IMultiMap<TKey, TValue>;：建立一個根據紅黑樹的多重對映。
  • CreateSortedMultiMap<TKey, TValue>(ownerships: TDictionaryOwnerships = []): IMultiMap<TKey, TValue>;：建立一個有序的多重對映。
程式碼示例
// 建立一個多重對映
var multiMap: IMultiMap<string, integer> := CreateMultiMap<string, integer>();

// 新增一些鍵值對
multiMap.Add('key1', 1);
multiMap.Add('key1', 2);
multiMap.Add('key2', 3);

// 取得所有與 'key1' 相關聯的值
var values: IReadOnlyCollection<integer> := multiMap.Items['key1'];
for value in values do
  writeln(value);

圖表翻譯

  graph LR
    A[多重對映] --> B[鍵值對]
    B --> C[值集合]
    C --> D[紅黑樹/雜湊表]
    D --> E[有序/無序]
    E --> F[支援多個值/唯一值]
    F --> G[多重對映工廠]
    G --> H[建立多重對映]
    H --> I[使用多重對映]

內容解密

多重對映是一種強大的集合型別，允許每個鍵與多個值相關聯。其複雜性來自於其實作細節，包括無序和有序的多重對映、支援多個值和唯一值等。透過使用 IMultiMap<TKey, TValue> 介面和 TCollections 工廠，可以輕鬆建立和使用多重對映。

多重對映（Multimap）概述

多重對映（Multimap）是一種資料結構，允許一個鍵（Key）對應多個值（Value）。在本文中，我們將探討六種不同實作的多重對映，包括 MultiMap、HashMultiMap、TreeMultiMap、SortedMultiMap、SortedHashMultiMap 和 SortedTreeMultiMap。

多重對映的種類

每種多重對映都有其特點：

  • MultiMap：基本的多重對映實作，鍵和值的順序由插入順序決定。
  • HashMultiMap：使用雜湊表來儲存鍵和值，鍵的查詢時間複雜度為 O(1)。
  • TreeMultiMap：使用二元樹來儲存鍵和值，鍵的查詢時間複雜度為 O(log n)。
  • SortedMultiMap：鍵和值都按照排序順序儲存。
  • SortedHashMultiMap：結合了雜湊表和排序的優點，鍵的查詢時間複雜度為 O(1)，值的排序由雜湊表決定。
  • SortedTreeMultiMap：結合了二元樹和排序的優點，鍵的查詢時間複雜度為 O(log n)，值的排序由二元樹決定。

實作和演示

以下是使用 Delphi 實作的多重對映示例：

procedure TfrmSetMultiMap.TestMultiMap(const name: string; const mmap: IMultiMap<integer, string>);
var
  i: integer;
  ch: char;
  sLog, s: string;
begin
  // 新增鍵和值
  for i := 3 downto 1 do
    for ch := 'c' downto 'a' do
    begin
      mmap.Add(i, ch);
      mmap.Add(i, ch);
    end;

  // 輸出結果
  sLog := '';
  for i in mmap.Keys do
  begin
    if sLog <> '' then
      sLog := sLog + ', ';
    sLog := sLog + IntToStr(i) + ':';
    for s in mmap[i] do
      sLog := sLog + s;
  end;
  ListBox1.Items.Add(name + ': ' + sLog);
end;

procedure TfrmSetMultiMap.btnTestMultimapClick(Sender: TObject);
begin
  TestMultiMap('MultiMap', TCollections.CreateMultiMap<integer, string>);
  TestMultiMap('HashMultiMap', TCollections.CreateHashMultiMap<integer, string>);
  TestMultiMap('TreeMultiMap', TCollections.CreateTreeMultiMap<integer, string>);
  TestMultiMap('SortedMultiMap', TCollections.CreateSortedMultiMap<integer, string>);
  TestMultiMap('SortedHashMultiMap', TCollections.CreateSortedHashMultiMap<integer, string>);
  TestMultiMap('SortedTreeMultiMap', TCollections.CreateSortedTreeMultiMap<integer, string>);
end;

演算法複雜度

每種多重對映的演算法複雜度如下：

  • Access：不適用
  • Search：
    • 鍵：O(1)（正常多重對映），O(log n)（排序多重對映）
    • 值：O(n)
  • Insert：
    • 鍵：O(1)（正常多重對映），O(log n)（排序多重對映）
    • 值：O(1)（列表、雜湊表），O(log n)（二元樹）

最佳化程式碼

在上一章中，我們探討了 Spring4D 的資料集合類別。現在，我們將關注於最佳化程式碼，以提高執行效率。最佳化程式碼是指對程式碼進行修改，以提高其執行速度或效率。

Delphi 編譯器設定

在開始最佳化程式碼之前，應該先檢查 Delphi 編譯器設定。編譯器設定可以對程式碼的執行效率產生重大影響。要檢查編譯器設定，請開啟您的專案，然後選擇「Project | Options」選單項，或按下 Ctrl + Shift + F11 鍵。相關的設定可以在「Building | Delphi Compiler | Compiling」中找到。

編譯器設定選項

以下是幾個重要的編譯器設定選項：

  • 內聯控制：內聯控制是指編譯器是否將函式內聯化。內聯化可以提高執行效率，但也可能增加程式碼大小。
  • 最佳化：最佳化是指編譯器是否對程式碼進行最佳化。最佳化可以提高執行效率，但也可能影響除錯。
  • 記錄欄位對齊：記錄欄位對齊是指編譯器是否對記錄欄位進行對齊。對齊可以提高執行效率，但也可能增加記錄大小。
  • 斷言：斷言是指編譯器是否對程式碼進行斷言。斷言可以提高程式碼的正確性，但也可能影響執行效率。
  • 溢位檢查：溢位檢查是指編譯器是否對程式碼進行溢位檢查。溢位檢查可以提高程式碼的正確性，但也可能影響執行效率。
  • 範圍檢查：範圍檢查是指編譯器是否對程式碼進行範圍檢查。範圍檢查可以提高程式碼的正確性，但也可能影響執行效率。

內聯控制

內聯控制是指編譯器是否將函式內聯化。內聯化可以提高執行效率，但也可能增加程式碼大小。內聯控制可以在編譯器設定中進行設定，也可以在程式碼中使用指令進行控制。

最佳化

最佳化是指編譯器是否對程式碼進行最佳化。最佳化可以提高執行效率，但也可能影響除錯。最佳化可以在編譯器設定中進行設定，也可以在程式碼中使用指令進行控制。

記錄欄位對齊

記錄欄位對齊是指編譯器是否對記錄欄位進行對齊。對齊可以提高執行效率，但也可能增加記錄大小。記錄欄位對齊可以在編譯器設定中進行設定。

斷言

斷言是指編譯器是否對程式碼進行斷言。斷言可以提高程式碼的正確性，但也可能影響執行效率。斷言可以在編譯器設定中進行設定。

溢位檢查

溢位檢查是指編譯器是否對程式碼進行溢位檢查。溢位檢查可以提高程式碼的正確性，但也可能影響執行效率。溢位檢查可以在編譯器設定中進行設定。

範圍檢查

範圍檢查是指編譯器是否對程式碼進行範圍檢查。範圍檢查可以提高程式碼的正確性，但也可能影響執行效率。範圍檢查可以在編譯器設定中進行設定。

記錄欄位對齊

在 Delphi 中，記錄欄位對齊是一個重要的編譯選項，控制著記錄和類別中的欄位在記憶體中的佈局。這個選項可以設定為以下幾個值：關閉（Off）、位元組（Byte）、字（Word）、雙字（Double Word）和四倍字（Quad Word）。雖然設定名稱可能有些誤導，因為前兩個值實際上會產生相同的行為。

編譯指令

您可以使用以下編譯指令來變更記錄欄位對齊：

  • {$ALIGN 1}、{$ALIGN 2}、{$ALIGN 4}、{$ALIGN 8}和 {$ALIGN 16}，分別對應不同的對齊設定。
  • 也可以使用較短的形式：{$A1}、{$A2}、{$A4}、{$A8}和 {$A16}。

此外，還有兩個指令是為了向後相容而存在：{$A+}等同於 {$A8}（也是新程式的預設值），而 {$A-}則等同於 {$A1}。

注意事項

雖然您可以在程式碼中設定雙四倍字對齊（{$A16}），但是在編譯器選項設定中並不提供這個選項。

欄位對齊的控制

欄位對齊控制著記錄和類別中的欄位在記憶體中的佈局。假設我們有一個記錄，其第一個欄位的地址為 0：

type
  MyRecord = record
    Field1: Byte;
    Field2: Word;
    Field3: Integer;
  end;

在不同的對齊設定下，記錄中的欄位在記憶體中的佈局會有所不同。瞭解這些設定對於最佳化記憶體使用和提高程式效率非常重要。

實際應用

在實際應用中，瞭解記錄欄位對齊的原理可以幫助您更好地設計資料結構，特別是在需要跨平臺或與其他語言共用資料結構的情況下。例如，在某些情況下，您可能需要確保記錄的大小是某個特定值的倍數，以便於資料對齊和存取。

{$A4} // 設定對齊為 4 個位元組
type
  MyAlignedRecord = record
    Field1: Byte;
    Field2: Word;
    Field3: Integer;
  end;

這樣，MyAlignedRecord 型別的記錄將會根據設定的對齊規則進行佈局，從而影響記憶體的使用效率和存取速度。

記錄欄位對齊

在 Delphi 中，記錄欄位對齊是透過 $A 指令來控制的。這個指令可以設定記錄欄位的對齊方式，從而影響記錄的大小和儲存方式。

{$A1} 對齊

當使用 $A1 對齊時，記錄欄位會按照其宣告的順序儲存，沒有任何間隔或填充。這意味著每個欄位會緊跟著前一個欄位，沒有任何空間浪費。

例如，以下記錄的大小會是 19 bytes：

TRecord = record
  Field1: byte;
  Field2: int64;
  Field3: word;
  Field4: double;
end;

{$A2} 對齊

當使用 $A2 對齊時，記錄欄位會按照 word 邊界對齊。這意味著每個欄位的地址會是 word 的倍數。

例如，以下記錄的大小會是 20 bytes：

TRecord = record
  Field1: byte;
  Field2: int64;
  Field3: word;
  Field4: double;
end;

{$A4} 對齊

當使用 $A4 對齊時，記錄欄位會按照 double word 邊界對齊。這意味著每個欄位的地址會是 double word 的倍數。

例如，以下記錄的大小會是 24 bytes：

TRecord = record
  Field1: byte;
  Field2: int64;
  Field3: word;
  Field4: double;
end;

{$A8} 對齊

當使用 $A8 對齊時，記錄欄位會按照 quad word 邊界對齊。這意味著每個欄位的地址會是 quad word 的倍數。

例如，以下記錄的大小會是 32 bytes：

TRecord = record
  Field1: byte;
  Field2: int64;
  Field3: word;
  Field4: double;
end;

實際應用

在實際應用中，記錄欄位對齊可以影響記錄的大小和儲存方式。例如，在某些情況下，使用 $A1 對齊可以節省儲存空間，但可能會影響記錄的存取效率。

圖表翻譯：
  flowchart TD
    A[記錄欄位對齊] --> B[$A1 對齊]
    B --> C[記錄大小 = 19 bytes]
    A --> D[$A2 對齊]
    D --> E[記錄大小 = 20 bytes]
    A --> F[$A4 對齊]
    F --> G[記錄大小 = 24 bytes]
    A --> H[$A8 對齊]
    H --> I[記錄大小 = 32 bytes]

內容解密：

在上面的例子中，記錄欄位對齊的方式會影響記錄的大小和儲存方式。使用 $A1 對齊可以節省儲存空間，但可能會影響記錄的存取效率。使用 $A2、$A4 和 $A8 對齊可以提高記錄的存取效率，但可能會增加儲存空間的浪費。因此，開發者需要根據具體的情況選擇合適的記錄欄位對齊方式。

範圍檢查

範圍檢查是編譯器的一個選項，用於檢查陣列元素和字串字元的索引是否在有效範圍內。例如，當你存取 s[idx+1] 時，編譯器會檢查 idx+1 是否是一個有效的索引。

你可以使用 {RANGECHECKS ON} 和 {RANGECHECKS OFF} 編譯器指令（或 {R+} 和 {R-}）來開啟或關閉範圍檢查。

讓我們看一個例子。下面的程式碼中，第二個 for 迴圈存取 arr[101] 元素，但沒有任何錯誤，儘管最大陣列元素是 arr[100]。然而，第三個 for 迴圈會丟擲 ERangeCheck 例外當存取 arr[101]：

procedure TfrmCompilerOptions.btnRangeErrorClick(Sender: TObject);
var
  arr: array [1..100] of Integer;
  i: Integer;
begin
  for i := Low(arr) to High(arr) do
    arr[i] := i;

  {$R-}
  for i := Low(arr) to High(arr) do
    arr[i] := arr[i] + arr[i+1];

  {$R+}
  for i := Low(arr) to High(arr) do
    arr[i] := arr[i] + arr[i+1];
end;

這種檢查非常重要，所以我總是把它留在我的程式碼中，甚至在發布版本中。存取不存在的陣列或字串元素可能看起來不是很危險，但如果你正在寫入該元素呢？如果這不是被捕捉到的話，你的程式碼就會用無意義的值覆寫其他資料，導致非常難以找到問題！

警告：在舊版本的 Delphi 中，範圍檢查即使在除錯版本中也是關閉的。我強烈建議你開啟它！

那麼，這種檢查的「成本」是什麼呢？如 CompilerOptions 程式所示，它可以很顯著。在這個例子中，開啟範圍檢查會減慢程式碼的速度：

圖 5.4 – 比較程式碼在開啟或關閉範圍檢查的情況下執行

在這種情況下，關閉範圍檢查可以加快程式的速度。但我仍然建議你只對程式碼的關鍵部分關閉範圍檢查，而不是整個程式。並且，應該只在發布版本中這樣做。

這結束了這個很長但必要的部分，因為瞭解開發工具總是很好的。現在，我們可以轉到更有趣的東西 – 真正的程式設計。

提取共同表示式

這個下一個提示可能看起來很明顯，但它會很好地介紹我們到下一個主題。另外，它是一個真正的問題，經常出現在生產程式碼中。

ExtractCommonExpression 演示程式建立了一個列表框，包含 1,000 個條目，每個條目都是作者-標題的形式。點選「複雜表示式」按鈕會執行一段簡短的程式碼，反轉列表框中作者和標題的順序，以便顯示以標題-作者的形式：

玄貓.Button1Click(
  Sender: TObject);
var
  i: Integer;
  sw: TStopwatch;

內容解密：

上面的程式碼使用了範圍檢查和提取共同表示式的概念。範圍檢查可以幫助我們避免存取不存在的陣列或字串元素，而提取共同表示式可以幫助我們簡化程式碼和提高效率。

圖表翻譯：

  flowchart TD
    A[開始] --> B[範圍檢查]
    B --> C[提取共同表示式]
    C --> D[簡化程式碼]
    D --> E[提高效率]

這個圖表展示了範圍檢查和提取共同表示式的流程。首先，我們進行範圍檢查，以確保我們存取的陣列或字串元素是有效的。然後，我們提取共同表示式，以簡化程式碼和提高效率。最終，我們可以得到更簡單和高效的程式碼。

最佳化程式碼的重要性

在程式設計中，最佳化程式碼的效能是非常重要的。這不僅能夠提高程式的執行速度，還能夠減少系統資源的消耗。然而，最佳化程式碼並不是一件容易的事，需要對程式的邏輯和語言有深入的理解。

從程式碼效能最佳化和程式碼正確性兩方面來看，Delphi 的 Spring4D 資料集合類別以及編譯器選項提供了多種最佳化策略。深入理解這些策略，例如字典介面 IDictionary 的不同實作（雜湊表和紅黑樹）及其對應的存取複雜度差異、多重對映 IMultiMap 的靈活運用，以及編譯器選項中記錄欄位對齊 $ALIGN 和範圍檢查 $RANGECHECKS 的設定，能有效提升程式碼的執行效率和穩定性。

分析不同多重對映實作的效能差異，例如 HashMultiMap 與 TreeMultiMap 在鍵值查詢速度上的優劣，以及排序版本 SortedMultiMap、SortedHashMultiMap 和 SortedTreeMultiMap 的應用場景，能幫助開發者根據實際需求選擇最合適的資料結構，避免不必要的效能損耗。同時，合理設定記錄欄位對齊，能最佳化記憶體佈局，提高資料存取速度。

儘管範圍檢查 $RANGECHECKS 會帶來一定的效能開銷，但從長遠來看，玄貓認為開啟範圍檢查對確保程式碼的正確性和穩定性至關重要，尤其在處理可能導致記憶體錯誤的陣列和字串操作時。開發者應權衡效能和穩定性，在發布版本中謹慎地針對關鍵程式碼區段關閉範圍檢查。未來，隨著硬體效能的提升和編譯器技術的進步，範圍檢查的效能開銷預計會逐步降低，其重要性將更加凸顯。對於追求高效能的開發者，建議深入研究編譯器最佳化選項，例如程式碼內聯和提取共同表示式等技術，在保障程式碼正確性的前提下，最大程度地提升程式碼執行效率。持續關注 Delphi Spring4D 的發展，並積極探索新的最佳化技巧，將有助於開發者寫出更 robust 和高效的程式碼。

玄貓

玄貓

技術愛好者，專注於分享程式開發、雲端技術與 AI 應用的心得體會。