跳轉到

3.2 多路合併與替換選擇#

概念說明#

3.1 節的初始 run 每個只有 B 頁，但替換選擇（replacement selection）可以產生「平均 2B 頁」的初始 run，直接減少合併輪數。其原理來自一個精巧的觀察：我們不必等到緩衝填滿才能輸出——只要用一個最小堆持續維護 B 筆記錄，每讀入一筆新記錄就輸出堆頂，並依「新記錄是否小於最後輸出的值」決定它屬於當前 run 還是下一個 run。

此外，合併階段本身也有調校空間：多路合併的「路數」k 決定了合併輪數 log_k(N/B)，k 越大輪數越少，但每輪要在 k 個輸入之間做選擇，CPU 上需用最小堆達到 O(log k) 每筆。當 k 大到無法為每個輸入保留完整緩衝頁時，順序 I/O 會退化成小塊讀取，反而變慢——因此實務上 k 的上限由「B-1 個緩衝頁」決定，超大資料則改用多輪合併。

演算法步驟：替換選擇#

  1. 讀入 B 筆記錄建立最小堆，設 last_output = -∞。
  2. 輸出堆頂 x，令 last_output = x。
  3. 讀入下一筆 y：若 y ≥ last_output，把 y 放入堆（屬於當前 run）；否則把 y 移到「凍結區」（屬於下一個 run）。
  4. 堆空時，解凍凍結區成為新堆，開始新 run；輸入耗盡即結束。

Python 範例#

import heapq

def replacement_selection(records, B):
    it = iter(records)
    heap = []
    for _ in range(B):
        try: heapq.heappush(heap, next(it))
        except StopIteration: break
    runs, cur = [], []
    last = float("-inf"); frozen = []
    for y in it:
        x = heapq.heappop(heap)
        cur.append(x); last = x
        if y >= last: heapq.heappush(heap, y)
        else: frozen.append(y)
        if not heap:                       # 當前 run 結束
            runs.append(cur); cur = []
            heap = list(frozen)            # 解凍並重建堆
            heapq.heapify(heap)
            frozen = []
            last = float("-inf")
    if heap: cur += [heapq.heappop(heap) for _ in range(len(heap))]
    if cur: runs.append(cur)
    if frozen: runs += replacement_selection(frozen, B)
    return runs

data = [34, 8, 64, 51, 32, 21, 12, 90, 26, 73, 5, 47]
runs = replacement_selection(data, B=4)
for i, r in enumerate(runs):
    print(f"run{i}（長度 {len(r)}）: {r}")

以 B=4 處理上述亂數序列，平均 run 長度會明顯超過 4 筆；若輸入本來就「幾乎有序」（例如只被亂掉一點的日誌檔），甚至可能只產生 1 個 run，完全免去合併階段。

複雜度與 I/O 成本分析#

  • 替換選擇 CPU：O(N log B)。
  • 平均 run 長度 2B 頁（理論最佳期望值），run 數由 ⌈N/B⌉ 降為 ⌈N/2B⌉。
  • 當 ⌈N/2B⌉ ≤ B-1 時可單輪合併完成，總 I/O 從 2N(1+log_{B-1}(N/B)) 降為 2N + 2N = 4N。
  • 極端情況：輸入為完全逆序時 run 長度退化為 B（等於普通排序階段）。

練習#

  1. 用 B=3 對序列 [5,3,7,1,9,2,8,4,6] 執行替換選擇，手動列出每個 run。
  2. 證明或說明：輸入為隨機排列時，run 平均長度趨近 2B 的直覺理由。
  3. 將替換選擇的輸出接到 3.1 節的合併函式，比較兩種初始 run 產生法的總 I/O。