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

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

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

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

IBG(塊間隙)

讀寫(xiě)一塊信息的時(shí)間TI/O=ta+ntwta

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

tw

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

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

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

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

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

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

R1R2R3R4R5R6R7R8R9R1020002000200020002000400040002000外排序總時(shí)間：

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頁(yè)，當(dāng)前為第6頁(yè)。[提高外排序效率的途徑]

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

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

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

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

C=sc(n-1)=logkm

c(n-1)=log2m/log2k

c(n-1)

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

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

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

68689896

890915890109206812109201581210920681290109201581290142224151617921422242516179226383025501897263830501897

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

220

4

013690136901092068121092015812

10920681290109201581290142224151611921422242516119226383025501897263830501897

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

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

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

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

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

13690

0109206812

123456調(diào)整敗者樹(shù)的方法:將新補(bǔ)充的結(jié)點(diǎn)與其雙親結(jié)點(diǎn)比較,敗者留在該雙親結(jié)點(diǎn),勝者繼續(xù)向上直至樹(shù)根的雙親數(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頁(yè)，當(dāng)前為第12頁(yè)。7777

77790

0109206812

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

至少要有k個(gè)輸入緩沖區(qū)和一個(gè)輸出緩沖區(qū)數(shù)據(jù)結(jié)構(gòu)---第11章外部排序13建敗者樹(shù)的過(guò)程7-1初始化敗者樹(shù)調(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頁(yè)，當(dāng)前為第13頁(yè)。11.4置換-選擇排序[目標(biāo)]

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

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

(w個(gè)記錄)FO

為簡(jiǎn)化問(wèn)題，設(shè)每個(gè)物理塊存放一個(gè)記錄數(shù)據(jù)結(jié)構(gòu)---第11章外部排序14【北郵本科課程-數(shù)據(jù)結(jié)構(gòu)】ds11全文共21頁(yè)，當(dāng)前為第14頁(yè)。[示例]FOWA(4個(gè)記錄)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頁(yè)，當(dāng)前為第15頁(yè)。[置換-選擇排序的效果]所得初始排序段的長(zhǎng)度不等當(dāng)輸入文件記錄的關(guān)鍵字大小隨機(jī)分布時(shí)，初始?xì)w并段的長(zhǎng)度為內(nèi)存工作區(qū)大小w的兩倍[緩沖區(qū)及并行操作]

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

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

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)外通路長(zhǎng)度的2倍IO方案二方案一【北郵本科課程-數(shù)據(jù)結(jié)構(gòu)】ds11全文共21頁(yè)，當(dāng)前為第17頁(yè)。[最佳歸并樹(shù)的構(gòu)造]最佳歸并樹(shù)即k叉(階)哈夫曼樹(shù)。設(shè)初始?xì)w并段為m個(gè)，進(jìn)行k-路歸并1）若(m-1)mod(k-1)0

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