10.1 如何選擇資料結構#

概念說明#

選擇資料結構的流程可以濃縮成四問：

核心操作是什麼？ 查詢、插入刪除、取最值、區間統計、前綴匹配、集合分組……操作模式決定一切。
資料有無順序需求？ 需要有序輸出/範圍查詢 → 樹系；只要按鍵直取 → 雜湊表。
規模與資源？ 資料在記憶體放得下 → 一般結構；需外存/DB → B 樹系；嵌入式 → 環形緩衝等固定空間結構。
常數重要嗎？ 小資料（n < 幾百）用什麼都快，優先選最簡單的（通常是 list/dict）。

決策表#

你最常做…	首選	次選	典型複雜度
按位置存取、尾端增刪	list（動態陣列）	deque	O(1)
兩端增刪	deque	—	O(1)
鍵值查詢、去重	dict / set	—	O(1) 平均
有序遍歷 + 動態插入刪除	平衡樹（如 sortedcontainers）	跳躍串列	O(log n)
取最大/最小 + 動態插入	堆積（heapq）	有序陣列	O(log n)
前綴查詢、自動補全	Trie	排序 + 二分	O(L)
區間和/區間最值 + 更新	線段樹 / BIT	前綴和（唯讀）	O(log n)
分組、合併、連通性	併查集	鄰接串列 + BFS	近 O(1)
頻率統計	Counter（雜湊表）	—	O(n)
順序處理（先來先做）	deque 當佇列	—	O(1)
巢狀/回溯處理	list 當堆疊	—	O(1)

實作：一個選型推理的例子#

需求：「滑動視窗最大值」——串流中最近 k 個數的最大值，每來一個新數就要回報一次。

推理：需要「取最大」＋「過期淘汰」＋「有序性維持」。堆積刪除任意元素麻煩；用單調佇列（雙端佇列的變形）——佇列內保存「可能是未來最大值」的候選索引，值遞減：

from collections import deque

def sliding_max(a, k):
    dq = deque()          # 存索引，對應值遞減
    out = []
    for i, x in enumerate(a):
        while dq and a[dq[-1]] <= x:   # 比新值小的候選全淘汰
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:             # 過期的頭移除
            dq.popleft()
        if i >= k - 1:
            out.append(a[dq[0]])
    return out

print(sliding_max([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]

每個元素至多進出佇列一次，整體 O(n)——比「每步重新找最大」的 O(nk) 快了 k 倍。這就是「操作模式分析 → 結構改造」的完整推理。

常見誤區#

在 list 上做大量 in 測試：O(n) 每次，該換 set/dict。
用 list 當 FIFO 佇列：pop(0) 是 O(n)，該用 deque。
過度工程：三筆資料上線段樹，程式碼複雜度暴增卻毫無收益。先簡單、慢了再優化。
忽略常數：n=1000 時 O(n log n) 的 set 操作可能比 O(n) 的巧妙演算法慢；理論複雜度要搭配實測。

複雜度分析#

選型本身沒有複雜度，但「錯誤選型」的代價可以用放大實驗量化：把本節誤區逐一放大資料量，觀察耗時成長曲線與理論表格的吻合度。

練習#

針對以下需求各給出首選結構並說明理由：(a) 瀏覽器上一頁/下一頁；(b) 醫院叫號（重診優先）；(c) 輸入法候選詞；(d) 股票當日最高價查詢（支援新成交更新）。
對「滑動視窗最小值」改造單調佇列，並用亂序資料與暴力法對拍驗證正確性。
你寫的程式跑得慢，profiler 顯示 90% 時間在 x in list。請描述你的優化步驟與預期加速倍數。