數(shù)據(jù)結(jié)構(gòu)課件：第11章 外部排序VIP

1、第11章 外部排序1內(nèi)容10.1 外部排序的概念和方法10.2 多路平衡歸并排序10.3 置換-選擇排序10.4 最佳歸并樹210.1 外部排序的概念和方法外排序：基于外部存儲(chǔ)設(shè)備（或文件）的排序技術(shù)就是外排序。當(dāng)待排序的對象數(shù)目特別多時(shí)，在內(nèi)存中不能一次處理。必須把它們以文件的形式存放于外存，排序時(shí)再把它們一部分一部分調(diào)入內(nèi)存進(jìn)行處理。在排序過程中必須不斷地在內(nèi)存與外存之間傳送數(shù)據(jù)。外部存儲(chǔ)設(shè)備：磁帶、磁盤3外部排序方法基于磁盤進(jìn)行的排序多使用歸并排序方法。排序過程主要分為兩個(gè)階段：(1) 建立用于外排序的內(nèi)存緩沖區(qū)。根據(jù)它們的大小將輸入文件劃分為若干段，用某種內(nèi)排序方法對各段進(jìn)行排序。這些

2、經(jīng)過排序的段叫做初始?xì)w并段或初始順串(Run)。當(dāng)它們生成后被寫入外存。(2) 仿照內(nèi)排序中介紹的歸并樹模式，把第一階段生成的初始?xì)w并段加以歸并，一趟趟地?cái)U(kuò)大歸并段和減少歸并段個(gè)數(shù)，直到最后歸并成一個(gè)大歸并段（有序文件）為止。4假設(shè)有 u=10000 個(gè)記錄，分為 m=10 個(gè)段，每段有l(wèi)=1000 個(gè)記錄。R1R2R3R4R5R6R7R8R9R10R12R34R56R78R910R1234R5678R12345678R進(jìn)行 k=2 路歸并，則需要進(jìn)行 s=4 趟歸并?？倸w并趟數(shù) s 等于歸并樹的高度 log2m。s= log2m5再假設(shè)磁盤每個(gè)物理塊可容納 200 個(gè)記錄，則每趟 10000

3、 個(gè)記錄需要50次讀50次寫，共 100 次操作。全部排序共需 d = 100*(4+1) = 500 次讀寫。假設(shè)有u=10000個(gè)記錄分為m=10段，每段有1000個(gè)記錄。進(jìn)行 k=2 路歸并，則需要進(jìn)行 s = 4 趟歸并?？倸w并趟數(shù) s = logkm （歸并樹的高度 ）外部排序需要的總時(shí)間為：tES = m*tIS + d*tIO + s*u*tmg內(nèi)部排序所需總時(shí)間外存讀寫所需總時(shí)間內(nèi)部歸并所需總時(shí)間則上例中tES = 10*tIS + 500*tIO + 4*10000*tmg6因?yàn)閠IO tmg，想要提高外排序的速度，應(yīng)減少 d.d 和歸并過程的關(guān)系：歸并路數(shù) k 總讀寫磁盤次

4、數(shù) d 歸并趟數(shù)s 2 500 4R1R2R3R4R5R6R7R8R9R10R1-5R67-10R1-10 5 300 2 10 200 1假設(shè)有u=10000個(gè)記錄分為m=10段，每段有1000個(gè)記錄。S越小，d越小7為了減小d，應(yīng)該減小s。 s = logkm tES = m*tIS + d*tIO + s*u*tmg內(nèi)部排序所需總時(shí)間外存讀寫所需總時(shí)間內(nèi)部歸并所需總時(shí)間8減小總讀寫次數(shù) d的途徑：增加歸并路數(shù)k減小初始段數(shù)m。10.2 多路平衡歸并排序 k-way Balanced merging 對于k 路平衡歸并，如果有 m 個(gè)初始?xì)w并段，需要?dú)w并s = logkm 趟。6路平衡歸并

5、樹：36個(gè)初始?xì)w并段減小總讀寫磁盤次數(shù) d的途徑1：增加歸并路數(shù)k910.2 多路平衡歸并排序做內(nèi)部 k 路歸并時(shí)，在 k 個(gè)對象中選擇最小者，需要順序比較 k-1 次。每趟歸并 n個(gè)對象需要做(n-1)*(k-1)次比較則 s 趟歸并總共需要的比較次數(shù)為：隨k增長而增長，增大k，會(huì)使得歸并的時(shí)間增大辦法：減小k 個(gè)對象中選最小的比較次數(shù)減小總讀寫磁盤次數(shù) d的途徑1：增加歸并路數(shù)k10敗者樹用“敗者樹”從 k 個(gè)歸并段中選最小者，當(dāng) k 較大時(shí) (k 6)，選出關(guān)鍵碼最小的對象只需比較 log2k 次。則s趟歸并總共需要的比較次數(shù)：利用敗者樹，只要內(nèi)存空間允許, 增大歸并路數(shù) k, 將有效地

6、減少歸并樹深度, 從而減少讀寫磁盤次數(shù) d, 提高外排序的速度。減小總讀寫磁盤次數(shù) d的途徑1：增加歸并路數(shù)k11敗者樹敗者樹是一棵正則的完全二叉樹，其中每個(gè)葉結(jié)點(diǎn)存放各歸并段在歸并過程中當(dāng)前參加比較的對象；每個(gè)非葉結(jié)點(diǎn)記憶它兩個(gè)子女結(jié)點(diǎn)中對象關(guān)鍵碼大的結(jié)點(diǎn)(即敗者)；typedef int LoserTreek;typedef structKeyType key; ExNode, Externalk+1; 12 Run0: 10, 15, Run1: 9, 18, Run2: 20, 22, Run3: 6, 15, Run4: 12, 37, 61512371015918202212209

7、10640213b3b4b0b1b2Run3Run4Run0Run1Run2ls4冠軍 (最小對象),輸出段3當(dāng)前對象選中l(wèi)s2ls1ls0ls3ls0ls1ls2ls3ls431024LoserTree13 6151237101591820221220910640213b3b4b0b1b2Run3Run4Run0Run1Run2ls4冠軍 (最小對象),輸出段1當(dāng)前對象ls2ls1ls0ls3153401自某葉結(jié)點(diǎn)bs到敗者樹根結(jié)點(diǎn)ls0的調(diào)整過程敗者樹-調(diào)整14/自某葉結(jié)點(diǎn)bs到敗者樹根結(jié)點(diǎn)ls0的調(diào)整算法void adjust ( LoserTree &ls, int s ) /從葉結(jié)點(diǎn)

8、 bs 開始，依次將當(dāng)前的 bs 與父結(jié)點(diǎn)指示的失敗者進(jìn)行比較 /將失敗者所在歸并段的段號(hào)記入父節(jié)點(diǎn)中。/ adjustt = (s + k) / 2; / lst 是bs的父節(jié)點(diǎn)while(t 0) if (bs.key blst.key) slst;t = t/2;ls0 = s;敗者樹-調(diào)整敗者樹的高度為 log2k，在每次調(diào)整，找下一 個(gè)具有最小關(guān)鍵碼對象時(shí), 最多做 log2k 次關(guān)鍵碼比較。15 615123710159182022b3b4b0b1b2Run3Run0Run1Run2ls4ls2ls1ls0ls3敗者樹-創(chuàng)建1)設(shè)bk為可能的最小值;2)設(shè)初值：lsi=k;1220

9、9106-55555b516初始化敗者樹12 615123710159182022b3b4b0b1b2Run3Run0Run1Run2ls4ls2ls1ls0ls33)依次從 bk-1,bk-2,b0出發(fā)調(diào)整失敗者1220910655555-b5455敗者樹-創(chuàng)建17創(chuàng)建敗者樹：插入b4（12）5方法：將bi與其父節(jié)點(diǎn)指示的上次比較的失敗者相比adjust (ls, 4 ) 6 615123710159182022b3b4b0b1b2Run3Run0Run1Run2ls4ls2ls1ls0ls33)依次從bk-1，bk-2,b0出發(fā)調(diào)整失敗者；1220910645555-b5435敗者樹-創(chuàng)建

10、518創(chuàng)建敗者樹：插入b3（6）方法：將bi與其父節(jié)點(diǎn)指示的上次比較的失敗者相比.adjust (ls, 3 ) 20 615123710159182022b3b4b0b1b2Run3Run0Run1Run2ls4ls2ls1ls0ls33)依次從bk-1，bk-2,b0出發(fā)調(diào)整失敗者；1220910643555-b52敗者樹-創(chuàng)建1955創(chuàng)建敗者樹：插入b2（20）方法：將bi與其父節(jié)點(diǎn)指示的上次比較的失敗者相比.adjust (ls, 2 ) 9 615123710159182022b3b4b0b1b2Run3Run0Run1Run2ls4ls2ls1ls0ls31220910643255

11、-b5152敗者樹-創(chuàng)建20創(chuàng)建敗者樹：插入b1（9）3)依次從bk-1，bk-2,b0出發(fā)調(diào)整失敗者；方法：將bi與其父節(jié)點(diǎn)指示的上次比較的失敗者相比.adjust (ls, 1 ) 10 615123710159182022b3b4b0b1b2Run3Run0Run1Run2ls4ls2ls1ls0ls31220910643215-b5130敗者樹-創(chuàng)建21創(chuàng)建敗者樹：插入b0（10）3)依次從bk-1，bk-2,b0出發(fā)調(diào)整失敗者；方法：將bi與其父節(jié)點(diǎn)指示的上次比較的失敗者相比.adjust (ls, 0 ) / 創(chuàng)建初始失敗者樹的算法void CreateLoserTree ( Lo

12、serTree &ls) /已知b0到bk-1為完全二叉樹 ls 的葉結(jié)點(diǎn)， /其中存有 k 個(gè)關(guān)鍵字；bk 為輔助節(jié)點(diǎn)。 /沿從葉結(jié)點(diǎn)到根結(jié)點(diǎn)的k條路徑將 ls 調(diào)整為敗者樹/ CreateLoserTree bk.key = MINKEY; /MINKEY為可能的最小值for ( i =0; i =0; -i ) Adjust( ls, i);敗者樹-創(chuàng)建22void k-Merge( LoserTree &ls, External &b ) /利用敗者樹將編號(hào)從0到k-1的k個(gè)輸入歸并到輸出段 /b0 到 bk-1 記錄 k 個(gè)輸入段中當(dāng)前記錄的關(guān)鍵字/ k-Mergek-merge 算

13、法for( i =0; i k; +i ) input( bi.key ); /輸入CreateLoserTree(ls); /創(chuàng)建初始敗者樹while ( bls0.key ! = MAXKEY) q = ls0; / q指示當(dāng)前最小關(guān)鍵字所在段號(hào)output(q); / 輸出q段中當(dāng)前記錄input(bq.key, q); / 輸入q段中下一個(gè)記錄Adjust(ls, q); / 調(diào)整敗者樹 /while23k-merge 算法當(dāng)然，歸并路數(shù) k 的選擇不是越大越好。因?yàn)闅w并路數(shù) k增大時(shí)，相應(yīng)需增加輸入緩沖區(qū)個(gè)數(shù)。如果可供使用的內(nèi)存空間不變，勢必要減少每個(gè)輸入緩沖區(qū)的容量，使內(nèi)外存交換數(shù)

14、據(jù)的次數(shù)增大。2410.3 置換選擇排序歸并的趟數(shù)：s = logkm段數(shù)m = 記錄總數(shù)n / 內(nèi)存可容納的記錄數(shù)目如果減小m，則需要增加內(nèi)存的使用量。但是內(nèi)存的限制是一定的，如何在不增加內(nèi)存的情況下減少 m 呢？在整個(gè)排序的過程中，選擇最小關(guān)鍵字和輸入輸出交叉或平行進(jìn)行。置換-選擇排序減小總讀寫磁盤次數(shù) d的途徑2：減小初始段數(shù)m.2510.3 置換選擇排序Replacement-Selection Sorting在整個(gè)排序的過程中，選擇最小關(guān)鍵字和輸入輸出交叉或平行進(jìn)行。設(shè)輸入文件FI中24個(gè)對象的關(guān)鍵碼序列為 51,49, 39, 46, 38, 29, 14, 61, 15, 30,

15、 1, 48, 52, 3, 63, 27, 4, 13, 89, 24, 46, 58, 33, 76假設(shè)內(nèi)存工作區(qū)WA可容納6個(gè)記錄，得：Run1：29, 38, 39, 46, 49, 51Run2: 1,14, 15, 30, 48, 61Run3: 3, 4, 13, 27, 52, 63Run4: 24, 33, 46, 58, 76, 89減小總讀寫磁盤次數(shù) d的途徑2：減小初始段數(shù)m.2610.3 置換選擇排序按照選擇和置換方法構(gòu)造初始排序段：過程的步驟如下： 從輸入文件FI中把w個(gè)對象讀入內(nèi)存WA中，并構(gòu)造敗者樹。 利用敗者樹在w中選擇一個(gè)關(guān)鍵碼最小的對象記為MINMAX。

16、將MINMAX記錄寫到輸出文件FO中。27FOWA (6)FI空空51,49, 39, 46, 38, 29, 14, 61, 15, 30, 1, 48, 52, 3, 63, 27, 4, 13, 89, 24, 46, 58, 33, 76空51,49, 39, 46, 38, 2914, 61, 15, 30, 1, 48, 52, 3, 63, 27, 4, 13, 89, 24, 46, 58, 33, 76282951,49, 39, 46, 38, 1461, 15, 30, 1, 48, 52, 3, 63, 27, 4, 13, 89, 24, 46, 58, 33, 76

17、29,3851,49, 39, 46,61, 1415, 30, 1, 48, 52, 3, 63, 27, 4, 13, 89, 24, 46, 58, 33, 7629,38,3951,49, 15, 46,61, 1430, 1, 48, 52, 3, 63, 27, 4, 13, 89, 24, 46, 58, 33, 7629,38,39,4651,49, 15, 30,61, 141, 48, 52, 3, 63, 27, 4, 13, 89, 24, 46, 58, 33, 7629,38,39,46,4951,1, 15, 30,61, 1448, 52, 3, 63, 27,

18、 4, 13, 89, 24, 46, 58, 33, 7629,38,39,46,49,5148,1, 15, 30,61, 1452, 3, 63, 27, 4, 13, 89, 24, 46, 58, 33, 7629,38,39,46,49,51,6148,1, 15, 30,52, 143, 63, 27, 4, 13, 89, 24, 46, 58, 33, 7610.3 置換選擇排序 若FI未讀完, 則從FI讀入下一個(gè)對象到WA中。從WA中所有比關(guān)鍵字MINMAX大的記錄中，選擇最小的記錄，作為新的MINMAX;重復(fù)35 , 直到WA中選不出新的MINMAX為止。此時(shí), 在輸出文

19、件FO中得到一個(gè)初始?xì)w并段, 在它最后加一個(gè)歸并段結(jié)束標(biāo)志。 重復(fù)26, 直到WA為空。所得結(jié)果為：Run1：29, 38, 39,46,49,51,61Run2: 1, 3, 14, 15, 27, 30, 48, 52, 63, 89Run3: 4, 13, 24, 33, 46 ,58, 762910.3 置換選擇排序在WA中選擇MINMAX記錄，需要用敗者樹實(shí)現(xiàn)。說明：（1）WA中的記錄作為敗者樹的外部節(jié)點(diǎn)，敗者樹中的根節(jié)點(diǎn)的父節(jié)點(diǎn)指示W(wǎng)A中關(guān)鍵字最小的記錄；（2）為了便于選出MINMAX記錄，為每個(gè)記錄除了關(guān)鍵字外，附加一個(gè)所在歸并段序號(hào)。在比較時(shí)，先比段號(hào)，段號(hào)小的為勝；（3）敗者

20、樹的建立可從設(shè)工作區(qū)中所有記錄的段號(hào)均為“零”開始，然后從FI中輸入w個(gè)記錄，自上而下調(diào)整敗者樹。300000000ls1ls0ls400關(guān)鍵碼段號(hào)000000ls500000ls2ls3置換選擇排序中的敗者樹初始化樹310000000ls1ls0ls40000511ls500000ls2ls351,49, 39, 46, 38, 29, 14, 61, 15, 30, 1, 48, 52, 3, 63, 27, 4, 13, 89, 24, 46, 58, 33, 76551149139134b2b3b4b5b0b14612381132910置換選擇排序中的敗者樹創(chuàng)建32MINMAX=292

21、9461239130ls1ls0ls444915511ls52913811ls2ls31420b2b3b4b5b0b11611351,49, 39, 46, 38, 29, 14, 61, 15, 30, 1, 48, 52, 3, 63, 27, 4, 13, 89, 24, 46, 58, 33, 76置換選擇排序中的敗者樹調(diào)整（排序）33在比較時(shí)，先比段號(hào)，段號(hào)小的為勝29383MINMAX103429461239113ls1ls0ls444915511ls51426110ls2ls31523b2b3b4b5b0b151,49, 39, 46, 38, 29, 14, 61, 15, 3

22、0, 1, 48, 52, 3, 63, 27, 4, 13, 89, 24, 46, 58, 33, 76置換選擇排序中的敗者樹調(diào)整（排序）34在比較時(shí)，先比段號(hào)，段號(hào)小的為勝2938MINMAX3941246302214493353529214ls1ls0ls434915511ls51426110ls2ls31524b2b3b4b5b0b151,49, 39, 46, 38, 29, 14, 61, 15, 30, 1, 48, 52, 3, 63, 27, 4, 13, 89, 24, 46, 58, 33, 76置換選擇排序中的敗者樹調(diào)整（排序）35在比較時(shí)，先比段號(hào)，段號(hào)小的為勝29

23、38MINMAX394630249123155148253416110.3 置換選擇排序當(dāng)輸入的對象序列已經(jīng)按關(guān)鍵碼大小排好序時(shí)，只生成一個(gè)初始?xì)w并段。若輸入文件有 n 個(gè)對象，生成初始?xì)w并段的時(shí)間在一般情況下，每輸出一個(gè)對象，對敗者樹進(jìn)行調(diào)整需要時(shí)間為O(log2w)。對于n 個(gè)對象，生成初始?xì)w并段的時(shí)間開銷是O(nlog2w)3610.4 最佳歸并樹歸并樹是描述歸并過程的 k 叉樹。因?yàn)槊恳淮巫?k 路歸并都需要有 k 個(gè)歸并段參加，因此，歸并樹是只有度為0和度為 k 的結(jié)點(diǎn)的正則 k 叉樹。示例：設(shè)有13個(gè)長度不等的初始?xì)w并段，其長度(對象個(gè)數(shù))分別為 0, 0, 1, 3, 5, 7,

24、 9, 13, 16, 20, 24, 30, 38其中長度為 0 的是空歸并段。對它們進(jìn)行 3 路歸并時(shí)的歸并樹。37此歸并樹的帶權(quán)路徑長度為 WPL(24+30+38+7+9+13)*2+ (16+20+1+3+5)*3 377。1620013536938139729030245483166路徑長度：在歸并過程中的讀對象次數(shù)WPL 為歸并過程中的總讀對象數(shù)總的讀寫對象次數(shù)為 2*WPL=754為得到正則k叉樹，增加空歸并段。3810.4 最佳歸并樹不同的歸并方案所對應(yīng)的歸并樹的帶權(quán)路徑長度各不相同。為了使得總的讀寫次數(shù)達(dá)到最少，需要改變歸并方案，重新組織歸并樹。將哈夫曼樹的思想擴(kuò)充到 k

25、叉樹的情形。3910.4 最佳歸并樹例如，假設(shè)有 m=6 個(gè)初始?xì)w并段, 其長度(對象個(gè)數(shù))分別為： 13, 16, 20, 24, 30, 38 做3路歸并。歸并樹是只有度為 0 和度為 3的結(jié)點(diǎn)的正則 3叉樹。 n0 = 2n3 + 1 n3 = (n0 - 1)2。假設(shè)需要增加的虛段數(shù)為 u，則 n3 =(m + u - 1) /2 為整數(shù) u = (m-1) % 24010.4 最佳歸并樹為使歸并樹成為一棵正則 k 叉樹，可能需要補(bǔ)入空歸并段。補(bǔ)空歸并段的方法為：歸并樹是只有度為 0 和度為 k 的結(jié)點(diǎn)的正則 k 叉樹，設(shè)度為 0 的結(jié)點(diǎn)有 n0個(gè)，度為 k的結(jié)點(diǎn)有 nk 個(gè)，則有： n0 = (k - 1)nk + 1 nk = (n0 -1)(k - 1)。 如果 (m-1) % (k-1) = 0，則說明這 m 個(gè)葉結(jié)點(diǎn)（即初始?xì)w并段）正好可