10.3 實戰案例與總結#

概念說明#

本節用三個貼近真實系統的案例整合全書：每個案例都先拆解需求成「操作模式」，再挑選與組合結構，最後驗證複雜度。

案例一：高頻詞統計（Top-K 問題）#

需求：從 100 萬行的日誌找出出現次數最多的 10 個詞。

選型：計數 → 雜湊表（Counter）；取前 10 → 大小為 10 的最小堆積（維護「目前的 Top 10」，新詞擠掉最小的）。O(n + m log k)。

import heapq
from collections import Counter

def top_k_words(lines, k=10):
    counter = Counter()
    for line in lines:
        counter.update(line.split())
    return heapq.nlargest(k, counter.items(), key=lambda kv: kv[1])

logs = ["error db timeout"] * 3000 + ["user login ok"] * 5000 + \
       ["warning disk full"] * 1200 + ["info heartbeat"] * 800
print(top_k_words(logs, 3))
# [('user', 5000), ('error', 3000), ('db', 3000)]

用到：雜湊表（4章）、堆積（7章）、Top-K 技巧（3章練習）。

案例二：簡易訂單系統#

需求：建立訂單（含編號、金額）、按編號查詢、按時間序出貨（FIFO）、隨時查最高金額訂單。

選型：編號查詢 → dict；FIFO 出貨 → deque 存編號；最高金額 → 堆積（配合惰性刪除）。

from collections import deque
import heapq

class OrderSystem:
    def __init__(self):
        self.orders = {}            # 編號 -> (金額, 狀態)
        self.queue = deque()        # 依建立順序
        self.max_heap = []          # (-金額, 編號)
        self._seq = 0

    def create(self, amount):
        self._seq += 1
        oid = f"O{self._seq:05d}"
        self.orders[oid] = (amount, "待出貨")
        self.queue.append(oid)
        heapq.heappush(self.max_heap, (-amount, oid))
        return oid

    def lookup(self, oid):
        return self.orders.get(oid)

    def ship_next(self):            # FIFO
        while self.queue:
            oid = self.queue.popleft()
            if self.orders[oid][1] == "待出貨":
                amt, _ = self.orders[oid]
                self.orders[oid] = (amt, "已出貨")
                return oid
        return None

    def top_amount(self):           # 最高金額（含已出貨，惰性檢查）
        while self.max_heap:
            neg_amt, oid = self.max_heap[0]
            if self.orders[oid][1] == "待出貨" and self.orders[oid][0] == -neg_amt:
                return oid, -neg_amt
            heapq.heappop(self.max_heap)   # 過期條目
        return None

s = OrderSystem()
for amt in [300, 1500, 700]:
    s.create(amt)
print(s.top_amount())      # ('O00002', 1500)
print(s.ship_next())       # O00001
print(s.top_amount())      # 仍是 ('O00002', 1500)

三種操作皆 O(1) 攤攤或 O(log n)，正是「組合多結構各司其職」的示範。

案例三：即時排行榜（含排名查詢）#

需求：玩家分數隨時更新、查前 K 名、查某玩家的名次。

選型：前 K 名 → 堆積即可；但「查名次」需要有序性 → 有序集合（以平衡樹為基底，本例用 sortedcontainers.SortedList；沒有第三方套件時可用 8 章的 BIT 依分數離散化統計）。展示 BIT 版：

class Leaderboard:
    def __init__(self, max_score=1000):
        self.max_score = max_score
        self.bit = [0] * (max_score + 2)     # BIT：分數 -> 人數
        self.scores = {}                     # 玩家 -> 分數

    def _add(self, i, d):
        while i <= self.max_score:
            self.bit[i] += d
            i += i & (-i)

    def _prefix(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & (-i)
        return s

    def update(self, player, score):
        if player in self.scores:            # 舊分數先移除
            self._add(self.scores[player], -1)
        self.scores[player] = score
        self._add(score, 1)

    def rank(self, player):                  # 名次 = 分數比我高的人數 + 1
        s = self.scores[player]
        return self._prefix(self.max_score) - self._prefix(s) + 1

lb = Leaderboard()
for name, sc in [("A", 90), ("B", 95), ("C", 90), ("D", 85)]:
    lb.update(name, sc)
print(lb.rank("B"))        # 1
print(lb.rank("A"))        # 2（90 分有兩人，先達者…本例同分並列）
lb.update("A", 97)
print(lb.rank("B"))        # 2

全書總結#

章別	結構	一句話記憶點
2	動態陣列/串列	連續換隨機存取，分散換彈性增刪
3	堆疊/佇列	限制端點，換來簡單與 O(1)
4	雜湊表	用雜湊函數直接定位，平均 O(1)
5	BST	左小右大，有序查詢的基礎
6	平衡樹	用旋轉/顏色/多鍵保證 O(log n)
7	堆積/圖/併查集	最值、關係、分組各有專用結構
8	Trie/線段樹/BIT	為前綴與區間特化的效率機器
9	圖演算法	走訪、最短路、生成樹
10	設計思維	操作模式決定結構，組合致勝

練習#

在 OrderSystem 增加 cancel(oid)（取消訂單，不出貨也不占最高額），確保 ship_next 與 top_amount 的正確性。
把 Leaderboard 擴充成 top_k(k)：回傳前 k 名玩家。提示：分數離散化後，用「前綴人數」逐段往下挖。
綜合題：設計「程式競賽評測系統」——支援提交（帶時間與分數）、按時間查前 K 高分、查某選手目前排名。寫出你的選型推理、實作與複雜度分析。