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

1、數(shù)據(jù)結(jié)構(gòu)第十一章外部排序本章內(nèi)容11.1 外存信息的存取11.2 外部排序的方法11.3 多路平衡歸并的實(shí)現(xiàn)11.4 置換-選擇排序11.5 最佳歸并樹11-2 11.1 外存信息的存取常用的外存儲(chǔ)器分類：順序存取的設(shè)備（如磁帶）；隨機(jī)存取的設(shè)備（如磁盤）。常用的外存儲(chǔ)器是磁表面存儲(chǔ)器, 信息記錄在一薄層磁性材料的表面上, 這層材料附著于載體表面, 隨著載體作高速旋轉(zhuǎn)或直線運(yùn)動(dòng), 在運(yùn)動(dòng)過程中用磁頭進(jìn)行讀或?qū)憽Ｍ獯嫘畔⒌拇嫒√攸c(diǎn), 決定了外部排序的策略選擇。11-3 11.1 外存信息的存取磁帶信息的存取磁帶存儲(chǔ)器的工作原理和磁帶錄音機(jī)一樣, 不同之處在于它存儲(chǔ)的是數(shù)字信息而不是模擬信息。磁帶

2、上的信息在橫向分布、縱向分布以及首尾標(biāo)志等都一定的格式。以1/2英寸九道的磁帶為例, 每一橫排就可表示一個(gè)字符（8位+1個(gè)校驗(yàn)位）。縱向按區(qū)進(jìn)行存儲(chǔ), 區(qū)的長度不固定, 但有一個(gè)范圍, 例如2到4096字節(jié), 相鄰區(qū)之間有一定長度的間隔（IBG, Inter Block Gap）, 作為磁帶起停之用。記錄 1記錄 3記錄 211-4 11.1 外存信息的存取在磁帶上讀寫一塊信息所需的時(shí)間由兩部分組成：TI/O = ta + n twta為延遲時(shí)間, 即讀/寫頭到達(dá)傳輸信息所在物理快起始位置所需時(shí)間；tw為傳輸一個(gè)字符的時(shí)間。顯然, 延遲時(shí)間和信息在磁帶上的位置、當(dāng)前讀/寫頭所在的位置有關(guān)。所以

3、磁帶便宜、可反復(fù)使用、是一種順序存取設(shè)備, 但查找費(fèi)時(shí)、速度慢（尤其是查找末端記錄時(shí)）。11-5 11.1 外存信息的存取磁盤信息的存取磁盤是一種直接存取的存儲(chǔ)設(shè)備(DASD）。頁塊的讀寫時(shí)間：TI/O = tseek + tlatency + n twmtseek：尋道時(shí)間tlatency：等待時(shí)間twm：傳輸時(shí)間11-6 11.2 外部排序的方法外部排序基本上由兩個(gè)相對(duì)獨(dú)立的階段組成：首先, 按可用內(nèi)存大小, 將外存上含n個(gè)記錄的文件分成若干長度為l的子文件或段(segment), 依次讀入內(nèi)存并利用有效的內(nèi)部排序方法對(duì)它們進(jìn)行排序, 并將排序后得到的有序子文件重新寫入外存, 通常稱這些有

4、序子文件為歸并段或順串(run)；然后, 對(duì)這些歸并段進(jìn)行逐躺歸并, 使歸并段（有序的子文件）逐漸由小至大, 直到得到整個(gè)有序文件為止。11-7 11.2 外部排序的方法例：一文件含10000記錄, 通過10次內(nèi)部排序得到10個(gè)初始?xì)w并段R1R10, 其中每一段都含有1000個(gè)記錄。然后作兩兩歸并：R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 R1 R2 R3 R4 R5 R1 R2 R3 R1 R2 有序文件由10個(gè)初始?xì)w并段到一個(gè)有序文件, 共進(jìn)行了4趟歸并, 每一趟都從m個(gè)歸并段得到ceil(m/2)個(gè)歸并段。這種歸并方法稱為2-路平衡歸并。11-8 11.2 外部排序的

5、方法外存上信息的讀/寫是以“物理塊”為單位進(jìn)行的, 假設(shè)每個(gè)物理塊可以容納200個(gè)記錄, 則每一趟歸并需進(jìn)行50次“讀”和50次“寫”, 4趟歸并加上內(nèi)部排序時(shí)所需進(jìn)行的讀/寫使得在外排序中總共需進(jìn)行500次讀/寫。11-9 11.2 外部排序的方法外部排序所需總的時(shí)間 = 內(nèi)部排序（產(chǎn)生初始?xì)w并段）所需的時(shí)間(m tIS) + 外存信息讀寫的時(shí)間(d tIO) +內(nèi)部歸并所需的時(shí)間(s utmg)其中： tIS 是為得到一個(gè)初始?xì)w并段進(jìn)行內(nèi)部排序所需時(shí)間的均值； tIO 是進(jìn)行一次外存讀/寫時(shí)間的均值； utmg 是對(duì)u個(gè)記錄進(jìn)行內(nèi)部歸并所需時(shí)間； m 為經(jīng)過內(nèi)部排序之后得到的初始?xì)w并段的個(gè)

6、數(shù)； s 為歸并的趟數(shù)； d 為總的讀/寫次數(shù)。于是上例進(jìn)行外排序所需總的時(shí)間為：10 tIS + 500 tIO + 4x10000 tmg顯然tIO較tmg要大的多, 因此提高外排序的效率應(yīng)主要著眼于減少外存信息讀寫的次數(shù)d。11-10 11.2 外部排序的方法d和“歸并過程”的關(guān)系：若對(duì)上例進(jìn)行5路平衡歸并： R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 R1 R2 有序文件僅需兩趟歸并, 總的讀/寫次數(shù)便減少為：2x100+100=300, 比2路歸并減少了200次的讀/寫。對(duì)同一文件, 進(jìn)行外排序時(shí)所需讀/寫外存的次數(shù)和歸并的趟數(shù)s成正比。一般情況下, 對(duì)m個(gè)初始?xì)w并

7、段進(jìn)行k路平衡歸并時(shí), 歸并的趟數(shù)s=floor(logkm).可見：若能增加k或減少m便能減少s, 因此減少d.11-11 11.3 多路平衡歸并的實(shí)現(xiàn)對(duì)于2路歸并, 令兩個(gè)歸并段上有u個(gè)記錄, 每得到歸并后的一個(gè)記錄, 僅需一次比較即可, 因此得到含u個(gè)記錄的歸并段需進(jìn)行u-1次比較。對(duì)于k路歸并, 令u個(gè)記錄分布在k個(gè)歸并段上, 顯然, 歸并后的第一個(gè)記錄應(yīng)是k個(gè)歸并段中關(guān)鍵字最小的記錄, 這需要進(jìn)行k-1次比較, 得到u個(gè)記錄的歸并段, 共需(u-1)(k-1)次比較。由此, 對(duì)n個(gè)記錄的文件進(jìn)行外排序時(shí), 在內(nèi)部歸并過程中進(jìn)行的總的比較次數(shù)為s(k-1)(n-1)。假設(shè)所得初始?xì)w并段

8、為m個(gè), 則歸并過程中進(jìn)行比較的總的時(shí)間為：floor(logkm)(k-1)(n-1)tmg = floor(log2m/log2k)(k-1)(n-1)tmg由于(k-1)/log2k 隨 k 的增長而增長, 這將抵消由于增大k而減少外存信息讀寫時(shí)間所得效益。11-12 11.3 多路平衡歸并的實(shí)現(xiàn)在進(jìn)行k路歸并時(shí)利用“敗者樹(Tree of Loser)”, 則可使在k個(gè)記錄中選出關(guān)鍵字最小的記錄時(shí)僅需進(jìn)行floor(log2k)次比較, 從而使總的歸并時(shí)間變?yōu)椋篺loor(log2m)(n-1)tmg與k無關(guān), 不再隨k的增長而增長。11-13 11.3 多路平衡歸并的實(shí)現(xiàn)勝者樹及其使

9、用勝者進(jìn)入下一輪, 直至決出本次比賽的冠軍。決出冠軍之后, 充分利用上一次比賽的結(jié)果, 使得更快地挑出亞軍、第三名 。729597654挑出冠軍需要進(jìn)行 k-1 次比較, 此處需要比較 3 次。955320517654321055957299511-14 11.3 多路平衡歸并的實(shí)現(xiàn)勝者樹及其使用勝者進(jìn)入下一輪, 直至決出本次比賽的冠軍。決出冠軍之后, 充分利用上一次比賽的結(jié)果, 使得更快地挑出亞軍、第三名 。7291697654挑出亞軍需要進(jìn)行 log2k 次比較, 此處需要比較 2次。9773207176543210779167299711-15 11.3 多路平衡歸并的實(shí)現(xiàn)勝者樹及其使用

10、 勝者進(jìn)入下一輪, 直至決出本次比賽的冠軍。決出冠軍之后, 充分利用上一次比賽的結(jié)果, 使得更快地挑出亞軍、第三名 。 決出第一名需比較： k - 1 次 決出第二名需比較： log2k 次 決出第三名需比較： log2k 次 結(jié)果：采用勝者樹后, 從 k 個(gè)元素中挑選一個(gè)最小的元素僅需 log2k 次比較, 這時(shí)總的比較次數(shù)下降為：logkm log2k ( n - 1 ) tmg log2m ( n - 1 ) tmg 該結(jié)果和 k 無關(guān), 這是通過多用空間換來的。改進(jìn)：采用勝者樹, k個(gè)元素中最小的元素輸出之后, 從根結(jié)點(diǎn)到它的相應(yīng)的葉子結(jié)點(diǎn)路徑上的結(jié)點(diǎn)都需要進(jìn)行修改, 為了加快程序運(yùn)行

11、的速度產(chǎn)生了敗者樹。11-16 11.3 多路平衡歸并的實(shí)現(xiàn)敗者樹在父節(jié)點(diǎn)中記下剛進(jìn)行完的比賽中的敗者, 但同樣讓勝者去參加下一輪的競賽, 便得到一棵“敗者樹”。11-17 11.3 多路平衡歸并的實(shí)現(xiàn)下圖即為一棵實(shí)現(xiàn)5-路歸并的敗者樹ls04, 圖中方形結(jié)點(diǎn)表示葉子結(jié)點(diǎn)(也可看成是外結(jié)點(diǎn)), 分別為5個(gè)歸并段中當(dāng)前參加歸并的待選擇記錄的關(guān)鍵碼；敗者樹中根結(jié)點(diǎn)ls1的雙親結(jié)點(diǎn)ls0為“冠軍”, 在此指示各歸并段中的最小關(guān)鍵碼記錄為第三段中的記錄；結(jié)點(diǎn)ls3指示b1和b2兩個(gè)葉子結(jié)點(diǎn)中的敗者即是b2, 而勝者b1和b3(b3是葉子結(jié)點(diǎn)b3、b4和b0經(jīng)過兩場比賽后選出的獲勝者)進(jìn)行比較, 結(jié)點(diǎn)l

12、s1則指示它們中的敗者為b1。11-18 11.3 多路平衡歸并的實(shí)現(xiàn)5-路歸并的敗者樹例920ls0ls1ls3ls2ls4b0b1b2b4b36152512374810151591820202240213061210411-19 11.3 多路平衡歸并的實(shí)現(xiàn)在選得最小關(guān)鍵碼的記錄之后, 只要修改葉子結(jié)點(diǎn)b3中的值, 使其為同一歸并段中的下一個(gè)記錄的關(guān)鍵碼, 然后從該結(jié)點(diǎn)向上和雙親結(jié)點(diǎn)所指的關(guān)鍵碼進(jìn)行比較, 敗者留在該雙親, 勝者繼續(xù)向上直至樹根的雙親。如下圖所示。當(dāng)?shù)?個(gè)歸并段中第2個(gè)記錄參加歸并時(shí), 選得最小關(guān)鍵碼記錄為第一個(gè)歸并段中的記錄。為了防止在歸并過程中某個(gè)歸并段變?yōu)榭? 可以在

13、每個(gè)歸并段中附加一個(gè)關(guān)鍵碼為最大的記錄。當(dāng)選出的“冠軍”記錄的關(guān)鍵碼為最大值時(shí), 表明此次歸并已完成。11-20 11.3 多路平衡歸并的實(shí)現(xiàn)5-路歸并的敗者樹例920ls0ls1ls3ls2ls4b0b1b2b4b31525123748101515918202022402014151210311-21 11.3 多路平衡歸并的實(shí)現(xiàn)實(shí)現(xiàn)k-路歸并的敗者樹的初始化也容易實(shí)現(xiàn), 只要先令所有的非終端結(jié)點(diǎn)指向一個(gè)含最小關(guān)鍵碼的葉子結(jié)點(diǎn), 然后從各葉子結(jié)點(diǎn)出發(fā)調(diào)整非終端結(jié)點(diǎn)為新的敗者即可。下面程序中簡單描述了利用敗者樹進(jìn)行k-路歸并的過程, 為了突出如何利用敗者樹進(jìn)行歸并, 避開了外存信息存取的細(xì)節(jié),

14、 可以認(rèn)為歸并段已存在。typedef int LoserTreek; /敗者樹是完全二叉樹且不含葉子, 可采用順序存儲(chǔ)結(jié)構(gòu)typedef structKeyType key;ExNode, Externalk; /外結(jié)點(diǎn), 只存放待歸并記錄的關(guān)鍵碼11-22 11.3 多路平衡歸并的實(shí)現(xiàn)void K_Merge(LoserTree *ls, External *b) /k-路歸并處理程序利用敗者樹ls將編號(hào)從0到k-1的k個(gè)輸入歸并段中的記錄歸并到輸出歸并段b0/到bk-1為敗者樹上的k個(gè)葉子結(jié)點(diǎn), 分別存放k個(gè)輸入歸并段中當(dāng)前記錄的關(guān)鍵碼for(i=0;i0) if(bs.keyblst.

15、key) slst; /s指示新的勝者 t=t/2; ls0=s;void CreateLoserTree(LoserTree *ls)/建立敗者樹/已知b0到bk-1為完全二叉樹ls的葉子結(jié)點(diǎn)存有k個(gè)關(guān)/鍵碼,沿從葉子到根的k條路徑將ls調(diào)整為敗者樹 bk.key=MINKEY; /設(shè)MINKEY為關(guān)鍵碼可能的最小值 for(i=0;i0;i-) Adjust(ls, i); /依次從bk-1, bk-2, , b0出發(fā)調(diào)整敗者 最后要提及一點(diǎn), k值的選擇并非越大越好, 如何選擇合適的k是一個(gè)需要綜合考慮的問題。11-24 11.4 置換-選擇排序歸并的趟數(shù)不僅和k成反比, 也和m成正比,

16、 因此減少m是減少s的另一條途徑。這里m是外部文件經(jīng)過內(nèi)部排序之后得到的初始?xì)w并段的個(gè)數(shù), m=ceil(n/l)。若要減少m, 就需要增加l, 但是內(nèi)存的容量有限, 利用上一章內(nèi)排序的方法無法做到, 所以必須探索新的排序方法。置換-選擇排序(Replacement-Selection Sorting)是在樹形選擇排序的基礎(chǔ)上得來的, 它的特點(diǎn)是：在整個(gè)排序（得到所有初始?xì)w并段）的過程中, 選擇最?。ɑ蜃畲螅╆P(guān)鍵字和輸入、輸出交叉或平行進(jìn)行。11-25 11.4 置換-選擇排序假設(shè)初始待排文件為輸入文件FI, 初始?xì)w并段文件為輸出文件FO, 內(nèi)存工作區(qū)為WA, FO和WA的初始狀態(tài)為空, 并設(shè)

17、內(nèi)存工作區(qū)WA的容量為w個(gè)記錄, 則置換-選擇排序的操作過程為：從FI輸入w個(gè)記錄到工作區(qū)WA;從WA中選出其中關(guān)鍵字最小值的記錄, 記為MINIMAX記錄；將MINIMAX記錄輸出到FO中去；若FI不空, 則從FI輸入下一個(gè)記錄到WA中；從WA中所有關(guān)鍵字比MINIMAX記錄的關(guān)鍵字大的記錄中選出最小關(guān)鍵字記錄, 作為新的MINIMAX記錄；重復(fù)3-5, 直至在WA中選不出新的MINIMAX記錄為止, 由此得到一個(gè)初始?xì)w并段, 輸出一個(gè)歸并段的結(jié)束標(biāo)志到FO中去；重復(fù)2-6, 直至WA為空, 由此得到全部初始?xì)w并段。11-26 11.4 置換-選擇排序例如：初始文件含24個(gè)記錄, 關(guān)鍵字分別

18、為：51, 49, 39, 46, 38, 29, 14, 61, 15, 30, 1, 48, 52, 3, 63, 27, 4, 13, 89, 24, 46, 58, 33, 76假設(shè)內(nèi)存工作區(qū)可容納6個(gè)記錄，則用內(nèi)排序的方法可以得到4個(gè)初始段：RUN1: 29, 38, 39, 46, 49, 51RUN2: 1, 14, 15, 30, 48, 61RUN3: 3, 4, 13, 27, 52, 63RUN3: 24, 33, 46, 58, 76, 89而用置換-選擇排序，則可求得如下3個(gè)初始?xì)w并段：RUN1: 29, 38, 39, 46, 49, 51, 61RUN2: 1,

19、3, 14, 15, 27, 30, 48, 52, 63, 89RUN3: 4, 13, 24, 33, 46, 58, 7611-27 11.4 置換-選擇排序置換-選擇排序的過程 (見教材第300頁)：FOWAFI51, 49, 39, 46, 38, 29, 14, 61, 15, 30, 1, 48, 52, 3, 63, 27, 4, 13, 89, 24, 46, 58, 33, 7651, 49, 39, 46, 38, 2914, 61, 15, 30, 1, 48, 52, 3, 63, 27, 4, 13, 89, 24, 46, 58, 33, 762951, 49,

20、39, 46, 38, 1461, 15, 30, 1, 48, 52, 3, 63, 27, 4, 13, 89, 24, 46, 58, 33, 7629, 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,

21、 63, 27, 4, 13, 89, 24, 46, 58, 33, 7629, 38, 39, 46, 4951, 1, 15, 30, 61, 1448, 52, 3, 63, 27, 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, 761

22、1-28 11.4 置換-選擇排序在WA中選擇MINIMAX記錄的過程需利用“敗者樹”來實(shí)現(xiàn)。內(nèi)存工作區(qū)中的記錄作為敗者樹的外部節(jié)點(diǎn)，而敗者樹的根節(jié)點(diǎn)的父節(jié)點(diǎn)指示工作區(qū)中關(guān)鍵字最小的紀(jì)錄；為了便于選出MINIMAX記錄，為每一個(gè)記錄附設(shè)一個(gè)所在歸并段的序號(hào)，在進(jìn)行關(guān)鍵字的比較時(shí)，現(xiàn)比較段號(hào)，段號(hào)小的為勝者，段號(hào)相同的則關(guān)鍵字小的為勝者；敗者樹的建立可從設(shè)工作區(qū)中所有記錄的段號(hào)均為“0”開始，然后從FI逐個(gè)輸入w個(gè)記錄到工作區(qū)是，自下而上調(diào)整敗者樹，由于這些記錄的段號(hào)為“1”，則他們對(duì)于“0”段的記錄而言均為敗者，從而逐個(gè)填充到敗者樹的各節(jié)點(diǎn)中去。11-29 11.4 置換-選擇排序可以證明, 利用置換-選擇排序，初始?xì)w并段的平均長度可達(dá)內(nèi)存允許尺寸w的二倍。最小值 最大值值遞增記錄數(shù)記錄值分布按等概率當(dāng)前最小值段分界值展開的環(huán)路均 勻 下 雪W積雪(內(nèi)存容量