【北郵本科課程-數(shù)據(jù)結(jié)構(gòu)】ds11

第十一章外部排序引言11.1外存信息的存取11.2外部排序的基本方法—?dú)w并排序法11.3多路平衡歸并11.4置換-選擇排序11.5最佳歸并樹本章學(xué)習(xí)要點(diǎn)、習(xí)題數(shù)據(jù)結(jié)構(gòu)---第11章外部排序1【北郵本科課程-數(shù)據(jù)結(jié)構(gòu)】ds11全文共21頁，當(dāng)前為第1頁。[外部排序的應(yīng)用對象]保存在外存儲器上的信息量很大的數(shù)據(jù)記錄文件。[外排序與內(nèi)排序的差別]內(nèi)部排序充分利用內(nèi)存可以隨機(jī)存取的特點(diǎn)，如希爾排序中，相隔di的記錄關(guān)鍵字可作比較；堆排序中，完全二叉樹中的父R[i]與子R[2i]、R[2i+1]可比；快速排序中，需正向和逆向訪問記錄序列外存信息的定位和存取受其物理特性的限制[外部排序的實(shí)現(xiàn)手段]在排序過程中，進(jìn)行多次內(nèi)外存之間的數(shù)據(jù)交換數(shù)據(jù)結(jié)構(gòu)---第11章外部排序2【北郵本科課程-數(shù)據(jù)結(jié)構(gòu)】ds11全文共21頁，當(dāng)前為第2頁。11.1外部信息的存取11.1.1磁帶信息的存取屬于順序存取設(shè)備，只適用于存儲順序文件[工作原理]

磁帶不是連續(xù)運(yùn)轉(zhuǎn)設(shè)備，而是啟停設(shè)備

I/O操作以塊為單位塊1塊2塊3……1K~8KB/塊

IBG(塊間隙)

讀寫一塊信息的時間TI/O=ta+ntwta

：用于磁頭定位在物理塊起始位置的時間

tw

：傳輸一個字符的時間數(shù)據(jù)結(jié)構(gòu)---第11章外部排序3【北郵本科課程-數(shù)據(jù)結(jié)構(gòu)】ds11全文共21頁，當(dāng)前為第3頁。11.1.2磁盤信息的存取

屬于直接存取設(shè)備，適用于各類存儲形式的文件[工作原理]

磁盤可以是單片的，或有若干個盤片組成盤組磁道：盤片上的同心圓柱面：各盤面上半徑相同的磁道合在一起扇區(qū)：每個磁道等分為若干扇區(qū)(塊)讀取信息的過程：柱面號移動磁頭盤面號(磁道號)選定所用磁頭扇區(qū)/塊號磁盤一直高速旋轉(zhuǎn)，磁頭等待開始位置讀寫一塊信息的時間TI/O=tseek+tla+ntwtseek

：磁頭定位到磁道的時間()tla

：等待時間數(shù)據(jù)結(jié)構(gòu)---第11章外部排序4【北郵本科課程-數(shù)據(jù)結(jié)構(gòu)】ds11全文共21頁，當(dāng)前為第4頁。11.2外部排序的基本方法—?dú)w并排序法[步驟]1)生成若干初始?xì)w并串/順串(文件予處理)把含有n個記錄的文件，按內(nèi)存緩沖區(qū)大小分成若干長度為L的子文件/段；分別調(diào)入內(nèi)存用有效的內(nèi)排序方法排序后送回外存；2)多路合并對初始?xì)w并串逐趟合并，直至最后在外存上得到整個有序文件為止數(shù)據(jù)結(jié)構(gòu)---第11章外部排序5Ln【北郵本科課程-數(shù)據(jù)結(jié)構(gòu)】ds11全文共21頁，當(dāng)前為第5頁。[例]某文件共10000個記錄，設(shè)每個物理塊可以容納200個記錄，內(nèi)存緩沖區(qū)可以容納5個物理塊

1)經(jīng)過10次內(nèi)排序后得到10個初始?xì)w并段R1~R102)采用兩路歸并，需四趟可以得到排好序的文件

R1R2R3R4R5R6R7R8R9R1020002000200020002000400040002000外排序總時間：

80002000

內(nèi)排序：10tIS

10000

I/O操作：100tIO(排序)

+(100+80+80+100)tIO(歸并)=460tIO

內(nèi)部歸并：(10000+8000+8000+10000)tmg=46000tmg數(shù)據(jù)結(jié)構(gòu)---第11章外部排序6【北郵本科課程-數(shù)據(jù)結(jié)構(gòu)】ds11全文共21頁，當(dāng)前為第6頁。[提高外排序效率的途徑]

減少合并趟數(shù)s，以減少I/O次數(shù)s=logkm擴(kuò)大初始?xì)w并段長度，從而減少初始?xì)w并段個數(shù)m進(jìn)行多路(k路)歸并

設(shè)內(nèi)存緩沖區(qū)可容納5個物理塊，則可進(jìn)行4路歸并數(shù)據(jù)結(jié)構(gòu)---第11章外部排序7輸入緩沖區(qū)

輸出緩沖區(qū)內(nèi)存外存【北郵本科課程-數(shù)據(jù)結(jié)構(gòu)】ds11全文共21頁，當(dāng)前為第7頁。11.3多路(k路)平衡歸并[通過簡單比較進(jìn)行歸并存在的問題]

設(shè)記錄總數(shù)為n，初始?xì)w并段的個數(shù)為m，從k個記錄中選擇一個關(guān)鍵字最小的記錄時的比較次數(shù)為c則s趟內(nèi)部歸并總的比較次數(shù)為：

C=sc(n-1)=logkm

c(n-1)=log2m/log2k

c(n-1)

k，s，可減少I/O次數(shù)；

k，c=(k-1)，歸并效率[解決矛盾的方法]

——利用“敗者樹”選關(guān)鍵字最小的記錄此時c=log2k則C=log2m(n-1)，與k無關(guān)數(shù)據(jù)結(jié)構(gòu)---第11章外部排序8矛盾…12……k【北郵本科課程-數(shù)據(jù)結(jié)構(gòu)】ds11全文共21頁，當(dāng)前為第8頁。[勝者樹(樹形選擇排序)的缺陷]

68689896

890915890109206812109201581210920681290109201581290142224151617921422242516179226383025501897263830501897

7路合并勝者樹重構(gòu)后的勝者樹重構(gòu)勝者樹時，從根結(jié)點(diǎn)至新補(bǔ)入記錄的葉結(jié)點(diǎn)的路徑上的所有結(jié)點(diǎn)都必須更新。數(shù)據(jù)結(jié)構(gòu)---第11章外部排序9【北郵本科課程-數(shù)據(jù)結(jié)構(gòu)】ds11全文共21頁，當(dāng)前為第9頁。[敗者樹]5

220

4

013690136901092068121092015812

10920681290109201581290142224151611921422242516119226383025501897263830501897

7路合并敗者樹重構(gòu)后的敗者樹敗者樹的特點(diǎn)：記錄敗者，勝者參加下一輪比賽敗者樹的優(yōu)點(diǎn)：重構(gòu)時修改結(jié)點(diǎn)較少。數(shù)據(jù)結(jié)構(gòu)---第11章外部排序1001234564ls[0]5ls[0]1234560【北郵本科課程-數(shù)據(jù)結(jié)構(gòu)】ds11全文共21頁，當(dāng)前為第10頁。[數(shù)據(jù)結(jié)構(gòu)](依據(jù)：敗者樹為完全二叉樹)主：b[0..k]b[0..k-1]——k個葉結(jié)點(diǎn)，存放k個輸入歸并段中當(dāng)前參加歸并的記錄

b[k]——虛擬記錄，用于建敗者

該關(guān)鍵字取可能的最小值minkey輔：ls[0..k-1]——不含葉結(jié)點(diǎn)的敗者樹存放最后勝出的編號（ls[0]）以及所記錄的敗者編號[處理步驟]1)建敗者樹ls[0..k-1]2)重復(fù)直至k路歸并完畢

2.1)將b[ls[0]]寫至輸出歸并段

2.2)補(bǔ)充記錄(某歸并段變空時,補(bǔ))，調(diào)整敗者樹數(shù)據(jù)結(jié)構(gòu)---第11章外部排序11【北郵本科課程-數(shù)據(jù)結(jié)構(gòu)】ds11全文共21頁，當(dāng)前為第11頁。4520

13690

0109206812

123456調(diào)整敗者樹的方法:將新補(bǔ)充的結(jié)點(diǎn)與其雙親結(jié)點(diǎn)比較,敗者留在該雙親結(jié)點(diǎn),勝者繼續(xù)向上直至樹根的雙親數(shù)據(jù)結(jié)構(gòu)---第11章外部排序12以在b[4]補(bǔ)充15為例154與3比較4與2比較42與5比較25【北郵本科課程-數(shù)據(jù)結(jié)構(gòu)】ds11全文共21頁，當(dāng)前為第12頁。7777

77790

0109206812

123456[k-路歸并對內(nèi)存的要求]

至少要有k個輸入緩沖區(qū)和一個輸出緩沖區(qū)數(shù)據(jù)結(jié)構(gòu)---第11章外部排序13建敗者樹的過程7-1初始化敗者樹調(diào)整b[6]6調(diào)整b[5]5調(diào)整b[4]4調(diào)整b[3]34調(diào)整b[2]2調(diào)整b[1]124調(diào)整b[0]054【北郵本科課程-數(shù)據(jù)結(jié)構(gòu)】ds11全文共21頁，當(dāng)前為第13頁。11.4置換-選擇排序[目標(biāo)]

擴(kuò)大初始?xì)w并段長度，突破內(nèi)存工作區(qū)容量（設(shè)w個記錄）的限制。[置換-選擇排序原理]

內(nèi)存外存原始文件內(nèi)存工作區(qū)FIWA初始?xì)w并段文件

(w個記錄)FO

為簡化問題，設(shè)每個物理塊存放一個記錄數(shù)據(jù)結(jié)構(gòu)---第11章外部排序14【北郵本科課程-數(shù)據(jù)結(jié)構(gòu)】ds11全文共21頁，當(dāng)前為第14頁。[示例]FOWA(4個記錄)FI

空空36,21,33,87,23,7,62,16,54,43,29,…

空36,21,33,8723,7,62,16,54,43,29,…2136,23,33,877,62,16,54,43,29,…21,2336,7,33,8762,16,54,43,29,…21,23,3336,7,62,8716,54,43,29,…21,23,33,3616,7,62,8754,43,29,…21,23,33,36,6216,7,54,8743,29,…21,23,33,36,62,8716,7,54,4329,…21,23,33,36,62,87||716,29,54,43…

…

數(shù)據(jù)結(jié)構(gòu)---第11章外部排序15【北郵本科課程-數(shù)據(jù)結(jié)構(gòu)】ds11全文共21頁，當(dāng)前為第15頁。[置換-選擇排序的效果]所得初始排序段的長度不等當(dāng)輸入文件記錄的關(guān)鍵字大小隨機(jī)分布時，初始?xì)w并段的長度為內(nèi)存工作區(qū)大小w的兩倍[緩沖區(qū)及并行操作]

使輸入、輸出和內(nèi)部歸并三種操作同時進(jìn)行，也能提高總的外部排序時間。但應(yīng)綜合考慮緩沖區(qū)數(shù)目、工作區(qū)大小等參數(shù)的設(shè)置。數(shù)據(jù)結(jié)構(gòu)---第11章外部排序16內(nèi)存k個輸入緩沖區(qū)1個輸出緩沖區(qū)【北郵本科課程-數(shù)據(jù)結(jié)構(gòu)】ds11全文共21頁，當(dāng)前為第16頁。11.5最佳歸并樹[最佳歸并樹的引入]

進(jìn)行k路歸并時，初始?xì)w并段的不同搭配，會導(dǎo)致歸并過程中I/O的次數(shù)不同。設(shè)有9個初始?xì)w并段，記錄個數(shù)(長度)分別為：

9，30，12，18，3，17，2，6，241211215138323032599301218317262411912171824236(9+30+12+18+3+17+2+6+24)2[(2+3+6)3+(9+12+17+(51+38+32)2+18+24)2+301]2=484=446數(shù)據(jù)結(jié)構(gòu)---第11章外部排序173-路歸并所有葉結(jié)點(diǎn)加權(quán)外通路長度的2倍IO方案二方案一【北郵本科課程-數(shù)據(jù)結(jié)構(gòu)】ds11全文共21頁，當(dāng)前為第17頁。[最佳歸并樹的構(gòu)造]最佳歸并樹即k叉(階)哈夫曼樹。設(shè)初始?xì)w并段為m個，進(jìn)行k-路歸并1）若(m-1)mod(k-1)0

則需附加(k-1)-(m-1)mod(k-1)