本案例基於 .claude/lib/hook_validator.py 的實際程式碼，展示如何選擇正確的資料結構來優化成員查詢效能。

先備知識

問題背景

成員查詢的效能差異

在 Python 中，檢查某個元素是否存在於容器中（成員查詢）是最常見的操作之一：

1if item in container:
2    # 做某些事

但這行簡單的程式碼，背後的效能差異可能高達 100 倍以上，取決於 container 是什麼資料結構。

list 的成員查詢：O(n)

1my_list = [1, 2, 3, ..., n]
2if x in my_list:  # 最壞情況要檢查 n 個元素
3    ...

list 是有序的線性結構，Python 必須從頭開始逐一比對，直到找到目標或走完整個 list。

set 的成員查詢：O(1)

1my_set = {1, 2, 3, ..., n}
2if x in my_set:  # 平均只需要 1 次雜湊計算
3    ...

set 使用雜湊表（hash table）實作，透過計算元素的雜湊值直接定位，不受容器大小影響。

真實案例：測試檔案存在性檢查

hook_validator.py 的 check_test_exists 方法會檢查每個 Hook 是否有對應的測試檔案：

 1def check_test_exists(self, hook_path: Path) -> List[ValidationIssue]:
 2    """
 3    檢查對應的測試檔案是否存在
 4
 5    Args:
 6        hook_path: Hook 檔案路徑
 7
 8    Returns:
 9        list[ValidationIssue]: 發現的問題
10    """
11    issues = []
12
13    # 生成測試檔案名稱
14    hook_name = hook_path.stem
15    test_name = f"test_{hook_name.replace('-', '_')}.py"
16
17    # 測試檔案應該在 .claude/lib/tests/ 或 .claude/hooks/tests/
18    possible_test_paths = [
19        self.project_root / ".claude" / "lib" / "tests" / test_name,
20        self.project_root / ".claude" / "hooks" / "tests" / test_name,
21    ]
22
23    test_exists = any(p.exists() for p in possible_test_paths)
24
25    if not test_exists:
26        issues.append(
27            ValidationIssue(
28                level="info",
29                message=f"未找到對應的測試檔案: {test_name}",
30                suggestion=(
31                    f"建議在以下位置建立測試:\n"
32                    f"  .claude/lib/tests/{test_name}"
33                )
34            )
35        )
36
37    return issues

這個程式碼有一個隱藏的效能問題：當需要驗證大量 Hook 時，每次都要呼叫 p.exists() 進行檔案系統操作。

假設我們要驗證 100 個 Hook，而測試目錄下有 200 個測試檔案：

 1def validate_all_hooks(self, hooks_dir: Optional[str] = None) -> List[ValidationResult]:
 2    """驗證所有 Hook 檔案"""
 3    # ... 省略部分程式碼 ...
 4
 5    results = []
 6    for hook_file in sorted(hooks_dir.glob("*.py")):  # 100 個 Hook
 7        if hook_file.name.startswith("_"):
 8            continue
 9        results.append(self.validate_hook(str(hook_file)))
10        # 每個 validate_hook 會呼叫 check_test_exists
11        # check_test_exists 會呼叫 2 次 Path.exists()
12        # 總共：100 * 2 = 200 次檔案系統操作
13
14    return results

問題分析

原始程式碼的瓶頸：

  1. 重複的檔案系統操作：每個 Hook 都要呼叫 exists() 檢查測試是否存在
  2. 沒有快取：相同的檢查可能被重複執行
  3. 線性搜尋：如果測試清單很長，用 list 儲存會導致 O(n) 的查詢時間

進階解決方案

用 set 取代 list

核心思路：先掃描一次測試目錄，建立測試檔案的 set，然後用 O(1) 查詢取代檔案系統操作。

 1class HookValidator:
 2    """Hook 合規性驗證器（優化版）"""
 3
 4    def __init__(self, project_root: Optional[str] = None):
 5        if project_root is None:
 6            project_root = os.environ.get(
 7                "CLAUDE_PROJECT_DIR",
 8                os.getcwd()
 9            )
10        self.project_root = Path(project_root)
11
12        # 優化：預先建立測試檔案的 set
13        self._test_files_cache: Optional[set[str]] = None
14
15    @property
16    def test_files(self) -> set[str]:
17        """
18        取得所有測試檔案名稱（快取）
19
20        Returns:
21            set[str]: 測試檔案名稱集合
22        """
23        if self._test_files_cache is None:
24            self._test_files_cache = self._scan_test_files()
25        return self._test_files_cache
26
27    def _scan_test_files(self) -> set[str]:
28        """
29        掃描所有測試目錄，建立測試檔案集合
30
31        Returns:
32            set[str]: 測試檔案名稱集合
33        """
34        test_dirs = [
35            self.project_root / ".claude" / "lib" / "tests",
36            self.project_root / ".claude" / "hooks" / "tests",
37        ]
38
39        test_files = set()  # 使用 set 而非 list
40        for test_dir in test_dirs:
41            if test_dir.is_dir():
42                for test_file in test_dir.glob("test_*.py"):
43                    test_files.add(test_file.name)
44
45        return test_files
46
47    def check_test_exists(self, hook_path: Path) -> List[ValidationIssue]:
48        """
49        檢查對應的測試檔案是否存在（優化版）
50
51        使用 set 進行 O(1) 查詢，取代檔案系統操作。
52        """
53        issues = []
54
55        hook_name = hook_path.stem
56        test_name = f"test_{hook_name.replace('-', '_')}.py"
57
58        # 優化：O(1) 的 set 查詢，取代 O(n) 的 exists() 呼叫
59        test_exists = test_name in self.test_files
60
61        if not test_exists:
62            issues.append(
63                ValidationIssue(
64                    level="info",
65                    message=f"未找到對應的測試檔案: {test_name}",
66                    suggestion=(
67                        f"建議在以下位置建立測試:\n"
68                        f"  .claude/lib/tests/{test_name}"
69                    )
70                )
71            )
72
73        return issues

實作步驟

步驟 1：識別重複查詢

找出程式碼中哪些查詢會被重複執行：

1# 原始程式碼：每次驗證都會執行檔案系統操作
2for hook_file in hooks:
3    # possible_test_paths 中的 Path.exists() 被呼叫 2 次
4    test_exists = any(p.exists() for p in possible_test_paths)

步驟 2：收集所有可能的查詢目標

在初始化時掃描一次，建立完整的資料集：

 1def _scan_test_files(self) -> set[str]:
 2    """一次性掃描所有測試檔案"""
 3    test_files = set()
 4
 5    for test_dir in test_directories:
 6        if test_dir.is_dir():
 7            for test_file in test_dir.glob("test_*.py"):
 8                test_files.add(test_file.name)
 9
10    return test_files

步驟 3：用 set 取代 list

確保查詢容器是 set 而非 list：

1# 錯誤：用 list 儲存
2test_files = []  # O(n) 查詢
3for test_file in test_dir.glob("test_*.py"):
4    test_files.append(test_file.name)
5
6# 正確：用 set 儲存
7test_files = set()  # O(1) 查詢
8for test_file in test_dir.glob("test_*.py"):
9    test_files.add(test_file.name)

步驟 4：加入快取機制

避免重複掃描：

 1@property
 2def test_files(self) -> set[str]:
 3    """延遲初始化 + 快取"""
 4    if self._test_files_cache is None:
 5        self._test_files_cache = self._scan_test_files()
 6    return self._test_files_cache
 7
 8def clear_cache(self) -> None:
 9    """需要時可以清除快取"""
10    self._test_files_cache = None

效能測量

讓我們用 timeit 測量 list 和 set 的查詢效能差異：

 1import timeit
 2import random
 3import string
 4
 5def benchmark_membership_test():
 6    """比較 list 和 set 的成員查詢效能"""
 7
 8    # 準備測試資料
 9    def generate_filename():
10        return f"test_{''.join(random.choices(string.ascii_lowercase, k=10))}.py"
11
12    sizes = [100, 1000, 10000]
13
14    for size in sizes:
15        # 建立測試資料
16        items = [generate_filename() for _ in range(size)]
17        test_list = items.copy()
18        test_set = set(items)
19
20        # 準備查詢目標（一半存在、一半不存在）
21        existing_items = random.sample(items, min(100, size))
22        non_existing_items = [generate_filename() for _ in range(100)]
23        query_items = existing_items + non_existing_items
24        random.shuffle(query_items)
25
26        # 測量 list 查詢
27        def list_lookup():
28            for item in query_items:
29                _ = item in test_list
30
31        list_time = timeit.timeit(list_lookup, number=100)
32
33        # 測量 set 查詢
34        def set_lookup():
35            for item in query_items:
36                _ = item in test_set
37
38        set_time = timeit.timeit(set_lookup, number=100)
39
40        # 計算加速比
41        speedup = list_time / set_time
42
43        print(f"\n元素數量: {size:,}")
44        print(f"  list 查詢: {list_time:.4f} 秒")
45        print(f"  set 查詢:  {set_time:.4f} 秒")
46        print(f"  加速比:    {speedup:.1f}x")
47
48if __name__ == "__main__":
49    benchmark_membership_test()

典型執行結果：

 1元素數量: 100
 2  list 查詢: 0.0234 秒
 3  set 查詢:  0.0012 秒
 4  加速比:    19.5x
 5
 6元素數量: 1,000
 7  list 查詢: 0.2156 秒
 8  set 查詢:  0.0013 秒
 9  加速比:    165.8x
10
11元素數量: 10,000
12  list 查詢: 2.1847 秒
13  set 查詢:  0.0014 秒
14  加速比:    1560.5x

觀察重點：

  1. set 的查詢時間幾乎不變：無論元素數量是 100 還是 10,000，set 的查詢時間都在 0.001 秒左右
  2. list 的查詢時間線性增長：元素增加 10 倍，查詢時間也增加約 10 倍
  3. 加速比隨資料量增加：元素越多，set 的優勢越明顯

實際場景測試

模擬 Hook 驗證器的真實使用場景：

 1import timeit
 2from pathlib import Path
 3from typing import Optional, List, Set
 4
 5def benchmark_hook_validation():
 6    """模擬 Hook 驗證器的效能差異"""
 7
 8    # 模擬 200 個測試檔案
 9    test_files_list = [f"test_hook_{i}.py" for i in range(200)]
10    test_files_set = set(test_files_list)
11
12    # 模擬 100 個 Hook 要檢查
13    hooks_to_check = [f"hook_{i}" for i in range(100)]
14
15    def check_with_list():
16        """使用 list 進行查詢"""
17        results = []
18        for hook_name in hooks_to_check:
19            test_name = f"test_{hook_name}.py"
20            exists = test_name in test_files_list  # O(n)
21            results.append(exists)
22        return results
23
24    def check_with_set():
25        """使用 set 進行查詢"""
26        results = []
27        for hook_name in hooks_to_check:
28            test_name = f"test_{hook_name}.py"
29            exists = test_name in test_files_set  # O(1)
30            results.append(exists)
31        return results
32
33    # 測量效能
34    list_time = timeit.timeit(check_with_list, number=1000)
35    set_time = timeit.timeit(check_with_set, number=1000)
36
37    print(f"驗證 100 個 Hook（執行 1000 次）：")
38    print(f"  list 版本: {list_time:.4f} 秒")
39    print(f"  set 版本:  {set_time:.4f} 秒")
40    print(f"  加速比:    {list_time / set_time:.1f}x")
41
42if __name__ == "__main__":
43    benchmark_hook_validation()

典型執行結果：

1驗證 100 個 Hook（執行 1000 次）：
2  list 版本: 0.3892 秒
3  set 版本:  0.0087 秒
4  加速比:    44.7x

設計權衡

資料結構查詢插入刪除記憶體有序重複元素
listO(n)O(1)*O(n)低是允許
setO(1)O(1)O(1)高否不允許
dictO(1)O(1)O(1)高是**鍵不允許

*list 的 append 是 O(1)，insert 是 O(n)

**Python 3.7+ 的 dict 保持插入順序

記憶體使用比較

 1import sys
 2
 3def compare_memory():
 4    """比較 list 和 set 的記憶體使用"""
 5    items = list(range(10000))
 6
 7    list_version = items.copy()
 8    set_version = set(items)
 9
10    list_size = sys.getsizeof(list_version)
11    set_size = sys.getsizeof(set_version)
12
13    print(f"10,000 個整數：")
14    print(f"  list: {list_size:,} bytes")
15    print(f"  set:  {set_size:,} bytes")
16    print(f"  set/list 比率: {set_size / list_size:.2f}x")
17
18# 輸出：
19# 10,000 個整數：
20#   list: 87,624 bytes
21#   set:  524,512 bytes
22#   set/list 比率: 5.99x

權衡分析：

  • set 的記憶體使用約為 list 的 4-8 倍
  • 但查詢速度可以快 10-100 倍以上
  • 對於大多數場景，記憶體增加可以接受

何時該用 list？

  1. 需要保持順序：元素的順序很重要
  2. 需要重複元素：同一個值可能出現多次
  3. 需要索引存取：經常用 items[i] 存取
  4. 主要操作是遍歷：很少做成員查詢
  5. 資料量很小：少於 10 個元素時差異不大
1# 適合用 list 的場景
2commands = ["init", "build", "test", "deploy"]  # 需要順序
3scores = [95, 87, 95, 92, 87]  # 需要重複

何時該用 set？

  1. 主要操作是成員查詢：頻繁使用 in 運算子
  2. 需要去重：自動排除重複元素
  3. 需要集合運算：交集、聯集、差集
  4. 資料量較大：幾百個以上的元素
1# 適合用 set 的場景
2valid_extensions = {".py", ".js", ".ts"}  # 成員查詢
3seen_files = set()  # 追蹤已處理的檔案（去重）
4common_tags = tags_a & tags_b  # 集合運算

什麼時候該用這個技術？

適合使用的情況

  1. 頻繁的成員查詢：程式碼中有很多 if x in container 的檢查
  2. 查詢容器較大：容器有幾百個以上的元素
  3. 查詢頻率高：同一個容器被查詢多次
  4. 不需要元素順序：只關心「有沒有」而非「在哪裡」

不建議使用的情況

  1. 需要保持插入順序：用 list 或 dict
  2. 需要重複元素：用 list 或 collections.Counter
  3. 容器很小：10 個以下元素時差異不明顯
  4. 元素不可雜湊：list、dict 等 mutable 物件無法放入 set
1# 不可雜湊的物件無法用 set
2items = [[1, 2], [3, 4]]  # list of lists
3# set(items)  # TypeError: unhashable type: 'list'
4
5# 解法：轉換為 tuple
6items_set = {tuple(item) for item in items}  # OK

練習

基礎練習

  1. 實作去重函式：寫一個函式，用 set 去除 list 中的重複元素，同時保持原本的順序
 1def deduplicate_ordered(items: list) -> list:
 2    """
 3    去除重複元素，保持順序
 4
 5    Example:
 6        >>> deduplicate_ordered([3, 1, 2, 1, 3, 2])
 7        [3, 1, 2]
 8    """
 9    # Your implementation here
10    pass
  1. 優化單字計數器：以下程式碼檢查一段文字中有多少個「停用詞」，請用 set 優化它
 1STOP_WORDS = ["the", "a", "an", "is", "are", "was", "were", "be", "been",
 2              "being", "have", "has", "had", "do", "does", "did", "will",
 3              "would", "could", "should", "may", "might", "must", "can"]
 4
 5def count_stop_words_slow(text: str) -> int:
 6    """計算停用詞數量（待優化）"""
 7    words = text.lower().split()
 8    count = 0
 9    for word in words:
10        if word in STOP_WORDS:  # O(n) 查詢
11            count += 1
12    return count
13
14# 請優化這個函式
15def count_stop_words_fast(text: str) -> int:
16    """計算停用詞數量（優化版）"""
17    # Your implementation here
18    pass

進階練習

  1. 實作檔案比對工具：比較兩個目錄中的檔案，找出只在其中一個目錄存在的檔案
 1from pathlib import Path
 2
 3def compare_directories(dir1: Path, dir2: Path) -> dict:
 4    """
 5    比較兩個目錄的檔案
 6
 7    Returns:
 8        dict: {
 9            "only_in_dir1": set[str],
10            "only_in_dir2": set[str],
11            "in_both": set[str],
12        }
13
14    提示：使用 set 的交集、差集運算
15    """
16    # Your implementation here
17    pass
  1. 優化 Hook 驗證器：參考本文的優化方案，為 HookValidator 加入以下功能：
  • 快取測試檔案列表
  • 支援多個測試目錄
  • 在測試目錄變更時自動更新快取

上一章：LRU 快取 返回：案例研究索引