第十章外部排序-資料下載頁
2024-10-11 11:40本頁面
【導(dǎo)讀】外部排序的基本方法—?dú)w并排序法。保存在外存儲器上的信息量很大的數(shù)據(jù)記錄文件。內(nèi)部排序充分利用內(nèi)存可以隨機(jī)存取的特點(diǎn)，如。希爾排序中，相隔di的記錄關(guān)鍵字可作比較；堆排序中，完全二叉樹中父R[i]與子R[2i]，快速排序中，需正向和逆向訪問記錄序列。外存信息的定位和存取受其物理特性的限制。生成若干初始?xì)w并串/順串。把含有n個記錄的文件，按內(nèi)存緩沖區(qū)大小分成若干長度為L. 的子文件（段）；分別調(diào)入內(nèi)存用有效的內(nèi)排序方法排序后送回外存；對初始?xì)w并串逐趟合并，直至最后在外存上得到整個有序文件為止。擴(kuò)大初始?xì)w并段長度，從而減少初始?xì)w并段個數(shù)m. 進(jìn)行多路(k路)歸并。，可減少I/O次數(shù)；路徑上的所有結(jié)點(diǎn)都必須更新。調(diào)整敗者樹的方法:將新補(bǔ)充的結(jié)點(diǎn)與其雙親結(jié)點(diǎn)比較,輔：ls[0..k-1]——不含葉結(jié)點(diǎn)的敗者樹。重復(fù)下列操作直至k路歸并完畢。1)從FI輸入w個記錄到工作區(qū)WA；2)在FO中標(biāo)記一個歸并段開始；4)將minimax記錄輸出到FO中；若由于WA為空而未選出，則結(jié)束處理；
【正文】 ]指示的外部結(jié)點(diǎn)屬于當(dāng)前段，輸出該記錄； 否則 ,當(dāng)前段號 +1，輸出段標(biāo)后再輸出該記錄； 4)若 FI未空，從 FI補(bǔ)充記錄， 若補(bǔ)充 key此前輸出記錄的 key，則 rnum=當(dāng)前段號 +1 否則 rnum=當(dāng)前段號 否則補(bǔ)虛記錄： key=?。 rnum=當(dāng)前段號 +1； 5)調(diào)整敗者樹 轉(zhuǎn) 3）直至所有記錄被輸出 調(diào)整敗者樹原則： 段號小者為勝者 段號相同，關(guān)鍵字小的為勝者 置換 選擇排序的效果 ? 所得初始排序段的長度不等 ? 當(dāng)輸入文件記錄的關(guān)鍵字大小隨機(jī)分布時，初始?xì)w并段的平均長度為內(nèi)存工作區(qū)大小 w的兩倍 最 佳 歸 并 樹 最佳歸并樹 文件經(jīng)過置換 選擇排序之后，得到長度不等的初始?xì)w并段，進(jìn)行 k路歸并時，初始?xì)w并段的不同搭配，會導(dǎo)致歸并過程中 I/O的次數(shù) 不同。 設(shè)有 9個初始?xì)w并段，記錄個數(shù) (長度 )分別為： 9， 30， 12， 18， 3， 17， 2， 6， 24 121 121 51 38 32 30 32 59 9 30 12 18 3 17 2 6 24 11 9 12 17 18 24 2 3 6 (9+30+12+18+3+17+2+6+24)?2 [(2+3+6) ?3+(9+12+17 +(51+38+32) ?2 +18+24) ?2+30 ?1] ?2 =484 =446 3路歸并 所有葉結(jié)點(diǎn)加權(quán)外通路長度的 2倍 IO 方案二 方案一 最佳歸并樹的構(gòu)造 最佳歸并樹即 k叉 (階 )哈夫曼樹。 設(shè)初始?xì)w并段為 m個，進(jìn)行 k路歸并 1）若 (m1) mod (k1) ?0 則需附加 (k1) (m1) mod (k1) 個長度為 0的虛段，以使每次歸并都可以對應(yīng) k個段 2）按照哈夫曼樹的構(gòu)造原則（權(quán)值越小的結(jié)點(diǎn)離根結(jié)點(diǎn)越遠(yuǎn)）構(gòu)造最佳歸并樹。 k階哈夫曼樹 示例 長度分別為 2， 3， 6， 9， 12， 17， 18， 24的 8個初始?xì)w并段進(jìn)行 3路歸并，求最佳歸并樹。 91 20 24 47 5 6 9 12 17 18 0 2 3 I/O次數(shù)： [(2+3)?3 + (6+9+12+17+18)?2 + 24?1] ?2 = 326 作業(yè) 1. 假設(shè)一次 I/O的物理塊可容納 150個記錄，每次可對 750個記錄進(jìn)行內(nèi)部排序，那么對含有 150000個記錄的磁盤文件進(jìn)行 4路平衡歸并排序時，共需進(jìn)行多少次 I/O？ 選擇排序之后，得到長度分別為 47， 9， 31， 18， 4， 12， 23和 7（單位均為物理塊）的 8個初始?xì)w并段。試為 3路平衡歸并設(shè)計一個讀寫外存次數(shù)最少的歸并方案，并求出讀寫外存的次數(shù)。 ？
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1