第十章外部排序(參考版)
2024-10-15 11:40本頁面
【正文】 ？ 。 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個記錄進行內(nèi)部排序，那么對含有 150000個記錄的磁盤文件進行 4路平衡歸并排序時，共需進行多少次 I/O？ 選擇排序之后，得到長度分別為 47， 9， 31， 18， 4， 12， 23和 7（單位均為物理塊）的 8個初始歸并段。 設(shè)初始歸并段為 m個，進行 k路歸并 1）若 (m1) mod (k1) ?0 則需附加 (k1) (m1) mod (k1) 個長度為 0的虛段，以使每次歸并都可以對應(yīng) k個段 2）按照哈夫曼樹的構(gòu)造原則（權(quán)值越小的結(jié)點離根結(jié)點越遠）構(gòu)造最佳歸并樹。 rnum=當(dāng)前段號 +1； 5)調(diào)整敗者樹 轉(zhuǎn) 3）直至所有記錄被輸出 調(diào)整敗者樹原則： 段號小者為勝者 段號相同，關(guān)鍵字小的為勝者 置換 選擇排序的效果 ? 所得初始排序段的長度不等 ? 當(dāng)輸入文件記錄的關(guān)鍵字大小隨機分布時，初始歸并段的平均長度為內(nèi)存工作區(qū)大小 w的兩倍 最 佳 歸 并 樹 最佳歸并樹 文件經(jīng)過置換 選擇排序之后，得到長度不等的初始歸并段，進行 k路歸并時，初始歸并段的不同搭配，會導(dǎo)致歸并過程中 I/O的次數(shù) 不同。 [置換 選擇排序原理 ] 內(nèi)存 外存 原始文件 內(nèi)存工作區(qū) FI WA 初始歸并段文件 (w個記錄 ) FO 為簡化問題，設(shè)每個物理塊存放一個記錄 1) 從 FI輸入 w個記錄到工作區(qū) WA； 2) 在 FO中標(biāo)記一個歸并段開始； 3) 從 WA中選出最小關(guān)鍵字記錄，記為 minimax記錄； 4) 將 minimax記錄輸出到 FO中； 5) 從 FI輸入下一個記錄到 WA中； 6) 在 WA中的關(guān)鍵字比 minimax大的記錄中選出關(guān)鍵字最小的記錄 ) 若不能選到，在 FO中標(biāo)記一個歸并段結(jié)束； 若由于 WA為空而未選出，則結(jié)束處理； 否則，標(biāo)記下一個歸并段開始，轉(zhuǎn) 3) ) 否則，將選出的記錄作為新的 minimax記錄，轉(zhuǎn) 4) [示例 ]利用敗者樹 (教材 303頁圖 ) FO WA(4個記錄 ) FI 空 空 36,21,33,87,23,7,62,16, 54,43,29,… 空
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1