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

數(shù)據(jù)結(jié)構(gòu) 第十一章 外部排序,本章內(nèi)容 11.1 外存信息的存取 11.2 外部排序的方法 11.3 多路平衡歸并的實(shí)現(xiàn) 11.4 置換-選擇排序 11.5 最佳歸并樹(shù),11-3,11.1 外存信息的存取,常用的外存儲(chǔ)器分類(lèi)： 順序存取的設(shè)備（如磁帶）； 隨機(jī)存取的設(shè)備（如磁盤(pán)）。 常用的外存儲(chǔ)器是磁表面存儲(chǔ)器, 信息記錄在一薄層磁性材料的表面上, 這層材料附著于載體表面, 隨著載體作高速旋轉(zhuǎn)或直線(xiàn)運(yùn)動(dòng), 在運(yùn)動(dòng)過(guò)程中用磁頭進(jìn)行讀或?qū)憽?外存信息的存取特點(diǎn), 決定了外部排序的策略選擇。,11-4,11.1 外存信息的存取,磁帶信息的存取 磁帶存儲(chǔ)器的工作原理和磁帶錄音機(jī)一樣, 不同之處在于它存儲(chǔ)的是數(shù)字信息而不是模擬信息。 磁帶上的信息在橫向分布、縱向分布以及首尾標(biāo)志等都一定的格式。 以1/2英寸九道的磁帶為例, 每一橫排就可表示一個(gè)字符（8位+1個(gè)校驗(yàn)位）。 縱向按區(qū)進(jìn)行存儲(chǔ), 區(qū)的長(zhǎng)度不固定, 但有一個(gè)范圍, 例如2到4096字節(jié), 相鄰區(qū)之間有一定長(zhǎng)度的間隔（IBG, Inter Block Gap）, 作為磁帶起停之用。,11-5,11.1 外存信息的存取,在磁帶上讀寫(xiě)一塊信息所需的時(shí)間由兩部分組成： TI/O = ta + n tw ta為延遲時(shí)間, 即讀/寫(xiě)頭到達(dá)傳輸信息所在物理快起始位置所需時(shí)間； tw為傳輸一個(gè)字符的時(shí)間。 顯然, 延遲時(shí)間和信息在磁帶上的位置、當(dāng)前讀/寫(xiě)頭所在的位置有關(guān)。 所以磁帶便宜、可反復(fù)使用、是一種順序存取設(shè)備, 但查找費(fèi)時(shí)、速度慢（尤其是查找末端記錄時(shí)）。,11-6,11.1 外存信息的存取,磁盤(pán)信息的存取 磁盤(pán)是一種直接存取的存儲(chǔ)設(shè)備(DASD）。 頁(yè)塊的讀寫(xiě)時(shí)間：TI/O = tseek + tlatency + n twm tseek：尋道時(shí)間 tlatency：等待時(shí)間 twm：傳輸時(shí)間,11-7,11.2 外部排序的方法,外部排序基本上由兩個(gè)相對(duì)獨(dú)立的階段組成： 首先, 按可用內(nèi)存大小, 將外存上含n個(gè)記錄的文件分成若干長(zhǎng)度為l的子文件或段(segment), 依次讀入內(nèi)存并利用有效的內(nèi)部排序方法對(duì)它們進(jìn)行排序, 并將排序后得到的有序子文件重新寫(xiě)入外存, 通常稱(chēng)這些有序子文件為歸并段或順串(run)； 然后, 對(duì)這些歸并段進(jìn)行逐躺歸并, 使歸并段（有序的子文件）逐漸由小至大, 直到得到整個(gè)有序文件為止。,11-8,11.2 外部排序的方法,例：一文件含10000記錄, 通過(guò)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è)歸并段。這種歸并方法稱(chēng)為2-路平衡歸并。,11-9,11.2 外部排序的方法,外存上信息的讀/寫(xiě)是以“物理塊”為單位進(jìn)行的, 假設(shè)每個(gè)物理塊可以容納200個(gè)記錄, 則每一趟歸并需進(jìn)行50次“讀”和50次“寫(xiě)”, 4趟歸并加上內(nèi)部排序時(shí)所需進(jìn)行的讀/寫(xiě)使得在外排序中總共需進(jìn)行500次讀/寫(xiě)。,11-10,11.2 外部排序的方法,外部排序所需總的時(shí)間 = 內(nèi)部排序（產(chǎn)生初始?xì)w并段）所需的時(shí)間(m tIS) + 外存信息讀寫(xiě)的時(shí)間(d tIO) +內(nèi)部歸并所需的時(shí)間(s utmg) 其中： tIS 是為得到一個(gè)初始?xì)w并段進(jìn)行內(nèi)部排序所需時(shí)間的均值； tIO 是進(jìn)行一次外存讀/寫(xiě)時(shí)間的均值； utmg 是對(duì)u個(gè)記錄進(jìn)行內(nèi)部歸并所需時(shí)間； m 為經(jīng)過(guò)內(nèi)部排序之后得到的初始?xì)w并段的個(gè)數(shù)； s 為歸并的趟數(shù)； d 為總的讀/寫(xiě)次數(shù)。 于是上例進(jìn)行外排序所需總的時(shí)間為：10 tIS + 500 tIO + 4x10000 tmg 顯然tIO較tmg要大的多, 因此提高外排序的效率應(yīng)主要著眼于減少外存信息讀寫(xiě)的次數(shù)d。,11-11,11.2 外部排序的方法,d和“歸并過(guò)程”的關(guān)系： 若對(duì)上例進(jìn)行5路平衡歸并： R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 R1 R2 有序文件 僅需兩趟歸并, 總的讀/寫(xiě)次數(shù)便減少為：2x100+100=300, 比2路歸并減少了200次的讀/寫(xiě)。對(duì)同一文件, 進(jìn)行外排序時(shí)所需讀/寫(xiě)外存的次數(shù)和歸并的趟數(shù)s成正比。一般情況下, 對(duì)m個(gè)初始?xì)w并段進(jìn)行k路平衡歸并時(shí), 歸并的趟數(shù)s=floor(logkm). 可見(jiàn)：若能增加k或減少m便能減少s, 因此減少d.,11-12,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)部歸并過(guò)程中進(jìn)行的總的比較次數(shù)為s(k-1)(n-1)。假設(shè)所得初始?xì)w并段為m個(gè), 則歸并過(guò)程中進(jìn)行比較的總的時(shí)間為： floor(logkm)(k-1)(n-1)tmg = floor(log2m/log2k)(k-1)(n-1)tmg 由于(k-1)/log2k 隨 k 的增長(zhǎng)而增長(zhǎng), 這將抵消由于增大k而減少外存信息讀寫(xiě)時(shí)間所得效益。,11-13,11.3 多路平衡歸并的實(shí)現(xiàn),在進(jìn)行k路歸并時(shí)利用“敗者樹(shù)(Tree of Loser)”, 則可使在k個(gè)記錄中選出關(guān)鍵字最小的記錄時(shí)僅需進(jìn)行floor(log2k)次比較, 從而使總的歸并時(shí)間變?yōu)椋?floor(log2m)(n-1)tmg 與k無(wú)關(guān), 不再隨k的增長(zhǎng)而增長(zhǎng)。,11-14,11.3 多路平衡歸并的實(shí)現(xiàn),勝者樹(shù)及其使用 勝者進(jìn)入下一輪, 直至決出本次比賽的冠軍。決出冠軍之后, 充分利用上一次比賽的結(jié)果, 使得更快地挑出亞軍、第三名 。,7,29,5,9,7,6,5,4,挑出冠軍 需要進(jìn)行 k-1 次比較, 此處需要比較 3 次。,9,5,5,3,2,0,5,1,11-15,11.3 多路平衡歸并的實(shí)現(xiàn),勝者樹(shù)及其使用 勝者進(jìn)入下一輪, 直至決出本次比賽的冠軍。決出冠軍之后, 充分利用上一次比賽的結(jié)果, 使得更快地挑出亞軍、第三名 。,7,29,16,9,7,6,5,4,挑出亞軍 需要進(jìn)行 log2k 次比較, 此處需要比較 2次。,9,7,7,3,2,0,7,1,11-16,11.3 多路平衡歸并的實(shí)現(xiàn),勝者樹(shù)及其使用 勝者進(jìn)入下一輪, 直至決出本次比賽的冠軍。決出冠軍之后, 充分利用上一次比賽的結(jié)果, 使得更快地挑出亞軍、第三名 。 決出第一名需比較： k - 1 次 決出第二名需比較： log2k 次 決出第三名需比較： log2k 次 結(jié)果：采用勝者樹(shù)后, 從 k 個(gè)元素中挑選一個(gè)最小的元素僅需 log2k 次比較, 這時(shí)總的比較次數(shù)下降為： logkm log2k ( n - 1 ) tmg log2m ( n - 1 ) tmg 該結(jié)果和 k 無(wú)關(guān), 這是通過(guò)多用空間換來(lái)的。 改進(jìn)：采用勝者樹(shù), k個(gè)元素中最小的元素輸出之后, 從根結(jié)點(diǎn)到它的相應(yīng)的葉子結(jié)點(diǎn)路徑上的結(jié)點(diǎn)都需要進(jìn)行修改, 為了加快程序運(yùn)行的速度產(chǎn)生了敗者樹(shù)。,11-17,11.3 多路平衡歸并的實(shí)現(xiàn),敗者樹(shù) 在父節(jié)點(diǎn)中記下剛進(jìn)行完的比賽中的敗者, 但同樣讓勝者去參加下一輪的競(jìng)賽, 便得到一棵“敗者樹(shù)”。,11-18,11.3 多路平衡歸并的實(shí)現(xiàn),下圖即為一棵實(shí)現(xiàn)5-路歸并的敗者樹(shù)ls04, 圖中方形結(jié)點(diǎn)表示葉子結(jié)點(diǎn)(也可看成是外結(jié)點(diǎn)), 分別為5個(gè)歸并段中當(dāng)前參加歸并的待選擇記錄的關(guān)鍵碼；敗者樹(shù)中根結(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)過(guò)兩場(chǎng)比賽后選出的獲勝者)進(jìn)行比較, 結(jié)點(diǎn)ls1則指示它們中的敗者為b1。,11-19,11.3 多路平衡歸并的實(shí)現(xiàn),5-路歸并的敗者樹(shù)例,9,20,ls0,ls1,ls3,ls2,ls4,b0,b1,b2,b4,b3,6 15 25,12 37 48,10 15 15,9 18 20,20 22 40,2,1,3,0,6,12,10,4,11-20,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ù)向上直至樹(shù)根的雙親。如下圖所示。當(dāng)?shù)?個(gè)歸并段中第2個(gè)記錄參加歸并時(shí), 選得最小關(guān)鍵碼記錄為第一個(gè)歸并段中的記錄。為了防止在歸并過(guò)程中某個(gè)歸并段變?yōu)榭? 可以在每個(gè)歸并段中附加一個(gè)關(guān)鍵碼為最大的記錄。當(dāng)選出的“冠軍”記錄的關(guān)鍵碼為最大值時(shí), 表明此次歸并已完成。,11-21,11.3 多路平衡歸并的實(shí)現(xiàn),5-路歸并的敗者樹(shù)例,9,20,ls0,ls1,ls3,ls2,ls4,b0,b1,b2,b4,b3,15 25,12 37 48,10 15 15,9 18 20,20 22 40,2,0,1,4,15,12,10,3,11-22,11.3 多路平衡歸并的實(shí)現(xiàn),實(shí)現(xiàn)k-路歸并的敗者樹(shù)的初始化也容易實(shí)現(xiàn), 只要先令所有的非終端結(jié)點(diǎn)指向一個(gè)含最小關(guān)鍵碼的葉子結(jié)點(diǎn), 然后從各葉子結(jié)點(diǎn)出發(fā)調(diào)整非終端結(jié)點(diǎn)為新的敗者即可。 下面程序中簡(jiǎn)單描述了利用敗者樹(shù)進(jìn)行k-路歸并的過(guò)程, 為了突出如何利用敗者樹(shù)進(jìn)行歸并, 避開(kāi)了外存信息存取的細(xì)節(jié), 可以認(rèn)為歸并段已存在。,typedef int LoserTreek; /敗者樹(shù)是完全二叉樹(shù)且不含葉子, 可采用順序存儲(chǔ)結(jié)構(gòu) typedef struct KeyType key; ExNode, Externalk; /外結(jié)點(diǎn), 只存放待歸并記錄的關(guān)鍵碼,11-23,11.3 多路平衡歸并的實(shí)現(xiàn),void K_Merge(LoserTree *ls, External *b) /k-路歸并處理程序利用敗者樹(shù)ls將編號(hào)從0到k-1的k個(gè)輸入歸并段中的記錄歸并到輸出歸并段b0 /到bk-1為敗者樹(shù)上的k個(gè)葉子結(jié)點(diǎn), 分別存放k個(gè)輸入歸并段中當(dāng)前記錄的關(guān)鍵碼 for(i=0;ik;i+) input(bi.key); /分別從k個(gè)輸入歸并段讀入該段當(dāng)前第一個(gè)記錄的關(guān)鍵碼到外結(jié)點(diǎn) CreateLoserTree(ls); /建敗者樹(shù)ls, 選得最小關(guān)鍵碼為b0.key while(bls0.key!=MAXKEY) q=ls0; /q指示當(dāng)前最小關(guān)鍵碼所在歸并段 output(q); /將編號(hào)為q的歸并段中當(dāng)前(關(guān)鍵碼為bq.key的記錄寫(xiě)至輸出歸并段) input(bq.key); /從編號(hào)為q的輸入歸并段中讀入下一個(gè)記錄的關(guān)鍵碼 Adjust(ls, q); /調(diào)整敗者樹(shù), 選擇新的最小關(guān)鍵碼 output(ls0); /將含最大關(guān)鍵碼MAXKEY的記錄寫(xiě)至輸出歸并段 ,11-24,11.3 多路平衡歸并的實(shí)現(xiàn),void Adjust(LoserTree *ls, int s) /選得最小關(guān)鍵碼記錄后, 從葉到根調(diào)整敗者樹(shù), /選下一個(gè)最小關(guān)鍵碼, 從葉子結(jié)點(diǎn)bs到根結(jié) /點(diǎn)ls0的路徑調(diào)整敗者樹(shù) t=(s+k)/2; /lst是bs的雙親結(jié)點(diǎn) while(t0) if(bs.keyblst.key) slst; /s指示新的勝者 t=t/2; ls0=s; ,void CreateLoserTree(LoserTree *ls) /建立敗者樹(shù) /已知b0到bk-1為完全二叉樹(shù)ls的葉子結(jié)點(diǎn)存有k個(gè)關(guān) /鍵碼,沿從葉子到根的k條路徑將ls調(diào)整為敗者樹(shù) 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è) 需要綜合考慮的問(wèn)題。,11-25,11.4 置換-選擇排序,歸并的趟數(shù)不僅和k成反比, 也和m成正比, 因此減少m是減少s的另一條途徑。這里m是外部文件經(jīng)過(guò)內(nèi)部排序之后得到的初始?xì)w并段的個(gè)數(shù), m=ceil(n/l)。 若要減少m, 就需要增加l, 但是內(nèi)存的容量有限, 利用上一章內(nèi)排序的方法無(wú)法做到, 所以必須探索新的排序方法。 置換-選擇排序(Replacement-Selection Sorting)是在樹(shù)形選擇排序的基礎(chǔ)上得來(lái)的, 它的特點(diǎn)是：在整個(gè)排序（得到所有初始?xì)w并段）的過(guò)程中, 選擇最?。ɑ蜃畲螅╆P(guān)鍵字和輸入、輸出交叉或平行進(jìn)行。,11-26,11.4 置換-選擇排序,假設(shè)初始待排文件為輸入文件FI, 初始?xì)w并段文件為輸出文件FO, 內(nèi)存工作區(qū)為WA, FO和WA的初始狀態(tài)為空, 并設(shè)內(nèi)存工作區(qū)WA的容量為w個(gè)記錄, 則置換-選擇排序的操作過(guò)程為： 從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-27,11.4 置換-選擇排序,例如：初始文件含24個(gè)記錄, 關(guān)鍵字分別為： 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, 51 RUN2: 1, 14, 15, 30, 48, 61 RUN3: 3, 4, 13, 27, 52, 63 RUN3: 24, 33, 46, 58, 76, 89 而用置換-選擇排序，則可求得如下3個(gè)初始?xì)w并段： RUN1: 29, 38, 39, 46, 49, 51, 61 RUN2: 1, 3, 14, 15, 27, 30, 48, 52, 63, 89 RUN3: 4, 13, 24, 33, 46, 58, 76,11-28,11.4 置換-選擇排序,置換-選擇排序的過(guò)程 (見(jiàn)教材第300頁(yè))：,11-29,11.4 置換-選擇排序,在WA中選擇MINIMAX記錄的過(guò)程需利用“敗者樹(shù)”來(lái)實(shí)現(xiàn)。 內(nèi)存工作區(qū)中的記錄作為敗者樹(shù)的外部節(jié)點(diǎn)，而敗者樹(shù)的根節(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ù)的建立可從設(shè)工作區(qū)中所有記錄的段號(hào)均為“0”開(kāi)始，然后從FI逐個(gè)輸入w個(gè)記錄到工作區(qū)是，自下而上調(diào)整敗者樹(shù)，由于這些記錄的段號(hào)為“1”，則他們對(duì)于“0”段的記錄而言均為敗者，從而逐個(gè)填充到敗者樹(shù)的各節(jié)點(diǎn)中去。,11-30,11.4 置換-選擇排序,可以證明, 利用置換-選擇排序，初始?xì)w并段的平均長(zhǎng)度可達(dá)內(nèi)存允許尺寸w的二倍。,最小值 最大值,值遞增,