當數據放不進記憶體
比較次數不足以描述大型檔案的排序成本:數據還要由儲存裝置分區塊讀入,再把結果寫回。順序傳輸往往比大量零散存取便宜;不過,要計算傳輸量,必須先講清楚每次傳輸的大小,以及每輪之間保存甚麼。
定義 20.1.1
(區塊傳輸模型)
固定的有限輸入檔有 筆記錄,剛好佔 個區塊,每個區塊含 筆。一次區塊傳輸是讀或寫一個完整區塊。工作記憶體容納 個記錄位置,其中 。鍵有全序,記錄的原始次序明確。算法在此模型中的成本是其區塊傳輸次數。
每個輸入串列的小型描述符與計數器另計。我們計數的是區塊傳輸,不是實際時間、比較、磁碟尋道或描述符的傳輸。區塊是計算單位,並不表示所有儲存裝置的延遲相同。
定義 20.1.2
(串列)
串列是儲存為連續完整區塊的一段有序記錄。
以下構造使每段恰含整數個完整區塊。若實際最後一塊未滿,可填補並記下有效記錄數;填補值絕不可當成數據。
產生串列並逐輪合併
令 ,。由 得 、。
- 每次讀取至多 個區塊,在記憶體內穩定排序後寫成一段串列,直至讀完 個區塊。穩定合併排序可使用同樣大小的輔助陣列,所需記錄位置不超過 。故最初有 段串列,依原始數據塊次序排列。
- 每一合併輪,把相鄰串列分組,每組至多 段。每個輸入預留一個區塊緩衝,另預留一個輸出緩衝。反覆選出各段目前首項中的最小鍵並輸出;某輸入緩衝用盡時才讀入下一塊,輸出緩衝滿時便寫出。鍵相同時先取較早的輸入串列;同一段內保持原有次序。每組寫成一段新串列。依本算法,即使某組只有一段也要複製。
- 對完整上一輪輸出重複合併,直到剩一段。若 ,毋須合併輪。每輪完成前須保留足夠儲存空間容納輸入和輸出。
緩衝共需至多 個記錄位置。保存最多 個首項的堆或錦標賽樹另需 個描述符,未計入 。若實作受嚴格位元組預算限制,應先預留描述符空間再重新計算扇入數。此外,已耗盡的串列須有獨立狀態,不能用一個合法最大鍵冒充結束標記。
常見錯誤
(把全部記憶體都用作輸入緩衝)
人們很容易想一次合併 段串列。這些輸入緩衝加一個輸出緩衝共需 個位置;由下取整的定義,,所以總是超出記憶體。例如 、 時,四個輸入緩衝加一個輸出緩衝需要 個位置。扇入數 明確保留了一個輸出塊。
定理 20.1.3
(正確性與穩定性)
在上述假設及算法下,每段產生的串列都是輸入某段連續區間的穩定有序排列,而最終串列是整個輸入的穩定有序排列。
證明
(對合併輪歸納)
初始串列是相鄰輸入片段的穩定有序排列,並按原始片段次序排列。考慮一個合併組,其輸入串列都是原始連續區間的穩定有序排列,並按這些區間的次序列出。每段尚未取出的元素都不小於該段目前首項,因此所有首項中最小者也是整組剩餘元素的最小者。逐一輸出便得到有序排列,且每筆恰好輸出一次。至於穩定性,取兩筆鍵相等的記錄。若它們來自同一段,該段次序得以保留,而那本來就是原始次序。若來自不同段,由於各段按次序覆蓋連續區間,較早段的記錄原本在另一筆之前;平手規則正是先輸出較早段。相鄰串列對應相鄰的原始位置區間,合併後仍然如此;歸納得每輪及最終結果都具上述性質。
歸納攜帶的不只是有序性,而平手規則需要的正是那額外資訊。
證明透視
局部相等鍵規則為何保持整體次序
有序性本身在合併下封閉,穩定性卻不然:它需要知道每筆記錄來自何處。因此證明攜帶更強的不變量:每段都是原始位置某段連續區間的穩定有序副本,且各段按區間次序排列。關鍵一步只用這個不變量一次:同組不同段中鍵相等時,較早段的所有記錄原本都在較後段之前,所以純粹局部的規則「先取較早的輸入串列」便保持整體原始次序。最小首項論證只用到每段有序;穩定性論證則用到每組由按次序排列的相鄰串列組成。若把不相鄰的串列分在同組,仍保持有序,卻可能破壞穩定性。
定理 20.1.4
(輪數與傳輸量)
令 ,包括 時的 。初始串列產生及所有合併輪共需恰好
次區塊傳輸。暫存空間可在輪與輪之間重用;這個數字包括寫出最終串列。
證明
(先數段,再數區塊)
若某輪開始有 段,完成後有 段。反覆向上取整後,第 輪的段數是 :兩者都是使 的最小整數 。所以首次剩一段所需輪數正是 。產生初始串列時,每一輸入區塊讀一次、寫一次。每個合併輪亦恰讀一次每個輸入區塊並寫一次每個輸出區塊;各組均由整塊組成,沒有捨棄記錄,故輸出仍有 塊。把初始的 次和之後 輪各 次相加,即得公式。這是指定算法的精確計數,並非所有排序算法都必須達到的下界。
概念視角組合
把各輪看成合併樹的層
把每個初始串列畫成一片葉,把每個合併組畫成一個節點,其子節點就是它消耗的串列。第 輪便是一棵有根樹的第 層:每個節點至多有 個子節點,第 層有 個節點,樹根在高度 。由於單一串列的組也會複製,每片葉的深度都恰為 。每一層把全部 個區塊重寫一次,所以合併各輪共需 次傳輸:輪數就是這棵樹的高度。
常見錯誤
(漏計產生串列的一輪)
計數是 ,不是 :任何合併開始前,產生串列已把每個區塊讀寫一次。對下面的六塊例子,,而算法實際進行 次傳輸。當 ,合併項為零,但排序仍需 次。
例題 20.1.5
(三段串列,一輪合併)
取 、,十二個輸入鍵依次為
此時 、、、。穩定排序三段得到 、 和 。一次三路合併產生 。第一個 5 來自較早的第一段,因此排在第三段的 5 前。初始輪讀六塊、寫六塊,合併輪同樣如此,合共 24 次傳輸。若最終數據直接串流交給下游而不寫出,輸出契約及計數便不同。
輪數只隨段數按對數增長,但每輪都要完整讀寫一次。
例題 20.1.6
(十段串列,三輪合併)
取 、、。同樣 、,故 ,即九段各兩塊、一段一塊。第一輪合併把串列分成 四組,產生四段;按算法,單段組也要複製。下一輪分成 兩組,產生兩段,第三輪產生一段。段數依次為 ,所以 ,因為 。算法共傳輸 次。
另一極端是完全不需要合併。
例題 20.1.7
(一段即可容納的檔案)
取 、、。此時 ,整個檔案作為同一個片段讀入、穩定排序後寫出:、。產生串列讀兩塊、寫兩塊,共 次傳輸。公式仍計入寫出最終串列,這是輸出契約的一部分。
反例模式
每段已排序不代表整個檔案已排序
聲稱:只要每段都已排序,把各段依次寫出便得到有序檔案。將 與 直接連接,所得次序中 8 在 2 前,故並未排序。相等鍵時隨意選一段也不一定穩定:若較早段含 、較後段含 ,先輸出 就顛倒了原始次序。正確性需要最小首項合併,穩定性需要先取較早段的平手規則,兩者須分別論證。
如何解讀界限
用二元堆選首項,每筆合併記錄需 次級別的選取工作,全部合併的比較工作為 ;記憶體內的穩定初始排序則為 次比較。不同裝置的區塊傳輸時間可以相差很遠,所以傳輸量本身不是運行時間的實測。壓縮、變長記錄、平行磁碟、非同步預取、系統快取及失效均不在模型內。增加扇入數可能減少輪數,卻增加緩衝與描述符壓力。失敗後重試還需要獨立的原子輸出與復原契約;不可把未完成輸出當成完成的串列。
練習與解答
快速檢查
(兩段有序鍵為 和 ,第一段在原檔較早。寫出穩定合併結果。)
每當目前首項相等時,套用平手規則。
解答 · 答案
鍵為 ;第一段的兩個 4 要按原次序排在第二段的 4 前。
快速檢查
(設 、、。求 、、、 及區塊傳輸次數。)
由定義計算 和 ,再反覆向上取整相除。
解答 · 答案
,,故 。由於 ,;段數依次為 。算法共傳輸 次。
快速檢查
(設 、。使至多一輪合併即足夠的最小整數 是多少?)
恰在 時一輪便足夠。
解答 · 答案
需要 ,其中 、。 時 、、。 時 、、。 時 、、。 時 、、,故 。答案是 ,共 次傳輸。