第十一章 外部排序

本文格式為Word版，下載可任意編輯——第十一章外部排序

第十一章外部排序外存信息的存取外部排序的方法多路平衡歸并的實(shí)現(xiàn)置換——選擇排序最正確歸并樹(shù)

11.1外部信息的存取計(jì)算機(jī)一般有兩種存儲(chǔ)器：內(nèi)存儲(chǔ)器(主存)和外存儲(chǔ)器(輔存)。內(nèi)存的信息可隨機(jī)存取，且存取速度快，但價(jià)格貴。容量小。外存儲(chǔ)器包括磁帶和磁盤(pán)(或磁鼓),前者為順序存取的設(shè)備，后者為隨機(jī)存取的設(shè)備。1.磁帶信息的存取2.磁盤(pán)信息的存取3.光盤(pán)信息的存取

11.2外部排序的方法外部排序基本上由兩個(gè)相對(duì)獨(dú)立的階段組成。

1.按可以用內(nèi)存大小，將外存上含n個(gè)記錄的文件分成若干長(zhǎng)度為L(zhǎng)的子文件或段(segment),依次讀入內(nèi)存并利用有效的內(nèi)部排序方法對(duì)它們進(jìn)行排序，2.將排序后得到的有序子文件重新寫(xiě)入外存，尋常稱(chēng)這些有序子文件為歸并段或順串(run);然后，對(duì)這些歸并進(jìn)行逐趟歸并，使歸并段(有序的子文件)逐漸有小變大，直至得到整個(gè)有序文件為止。

11.2外部排序的方法一般狀況下，外部排序所需總的時(shí)間

=內(nèi)部排序所需的時(shí)間+外存信息讀寫(xiě)的時(shí)間+內(nèi)部歸并所需的時(shí)間

m*tisd*tIOs*utmg

其中：tis是為得到一個(gè)初始?xì)w并段進(jìn)行排序所需時(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ù)。

11.2外部排序的方法例:有10000條記錄,通過(guò)10次內(nèi)部排序得到10個(gè)初始?xì)w并段R1-R10,每段有1000條記錄.

R1

R2R3R4R5R6R7R8R9R10R2’R1’’R1’’’有序文件R3’R2’’R4’R5’R3’’R2’’’

R1’

11.2外部排序的方法從上例中我們可以得到:一共歸并了4趟

外存信息讀寫(xiě)500次問(wèn)題:是否可以改進(jìn)減少外存信息讀寫(xiě)?可以采用多路歸并即:R1R2R3R4R5R6R7R8R9R10R1’有序文件R2’

一共歸并了2趟,外存讀寫(xiě)300次

11.2外部排序的方法結(jié)論:對(duì)同一文件,進(jìn)行外部排序時(shí)所需讀寫(xiě)外存的次數(shù)和歸并趟數(shù)s成正比.對(duì)m個(gè)初始?xì)w并段進(jìn)行k-路平衡歸并時(shí),歸并趟數(shù)為:s=向上取整(logkm)顯然:增加k可以減少s

11.3多路平衡歸并的實(shí)現(xiàn)為了減少歸并趟數(shù),我們?cè)龃髃.問(wèn)題:增大了k又會(huì)出現(xiàn)新的問(wèn)題.增加內(nèi)部歸并所需的時(shí)間,由于比較的元素多了,比較的次數(shù)也就多了.為減少比較次數(shù),解決方法我們引出:敗者樹(shù).敗者樹(shù)：在雙親結(jié)點(diǎn)中記錄下來(lái)剛進(jìn)行完的這場(chǎng)比賽中的敗者，而讓勝者去參與更高一層的比賽，便可得到一棵“敗者樹(shù)〞。

11.3多路平衡歸并的實(shí)現(xiàn)例:31

勝利者

失敗者0b0b3661525.

2b1991820.b

220

4

b412123748.

10

101516.

202240.

11.3多路平衡歸并的實(shí)現(xiàn)例:1301

勝利者

失敗者40b0b3151525.

2b1991820.b220

34

b412123748.

10

101516.

202240.

11.4置換-選擇排序問(wèn)題:是否可以不用內(nèi)部排序構(gòu)造初始?xì)w并段?例:若初始文件含有24個(gè)記錄，其的關(guān)鍵字為:51,49,39,46,38,29,14,61,15,1,48,52,3,63,27,4,1389,24,46,58,33,76。假設(shè)內(nèi)存工作區(qū)可容納6個(gè)記錄，則可得如下4個(gè)初始?xì)w并段：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

11.4置換-選擇排序置換-選擇排序就是新的構(gòu)造方法:上例用此法,可求得如下3個(gè)初始?xì)w并段：RUN1:29,38,39,46,49,51,61RUN2:1,3,14,15,27,30,48,52,63,89RUN3:4,13,24,33,46,58,76

問(wèn)題:怎樣構(gòu)造呢?

置換-選擇排序算法思想:初始化:輸入文件FI,輸出文件FO,內(nèi)存工作區(qū)為WA.FO和WA置空，內(nèi)存工作區(qū)為空，WA的容量可容納w個(gè)記錄.(1)從FI輸入w個(gè)記錄到工作區(qū)WA。(2)從WA中選出最小關(guān)鍵字記錄，記MIN記錄。(3)將MIN輸出到FO中去。(4)若FI不為空，則從FI輸入下一個(gè)記錄到WA中。(5)從WA中所有關(guān)鍵字比MIN大的記錄中選出最小關(guān)鍵字記錄，作為新的MIN記錄。(6)重復(fù)(3)—(5),直至在WA中選不出新的MIN為止，則得一初始?xì)w并段，輸出之。(7)重復(fù)(2)—(6),直至WA為空。則得全部初始?xì)w并段。

FO空空292929,3829,38

WA空51,49,39,46,38,2951,49,39,46,3851,49,39,46,38,1451,49,39,46,,1451,49,39,46,61,14

FI51,49,39,46,38,29,14,61,15,30,1,48,52,…14,61,15,30,1,48,52,3,63,27,4,…14,61,15,30,1,48,52,3,63,27,4,…61,15,30,1,48,52,3,63,27,4,…61,15,30,1,48,52,3,63,27,4,…15,30,1,48,52,3,63,27,4,…

29,38,3929,38,3929,38,39,4629,38,39,4629,38,39,46,4929,38,39,46,49,51

51,49,,46,61,1451,49,15,46,61,1451,49,15,,61,1451,49,15,30,61,1451,1,15,30,61,1448,1,15,30,61,14

15,30,1,48,52,3,63,27,4,…30,1,48,52,3,63,27,4,…30,1,48,52,3,63,27,4,…1,48,52,3,63,27,4,…48,52,3,63,27,4,…52,3,63,27,4,…

FO29,38,39,46,49,51,61

WA48,1,15,30,52,143,63,27,4,…

FI3,63,27,4,…63,27,4,…27,4,…4,……………

29,38,39,46,49,51,6148,1,15,30,52,1411,31,3,141,3,14,15……

48,3,15,30,52,1448,63,15,30,52,1448,63,15,30,52,2748,63,4,30,52,27……

RUN1:29,38,39,46,49,51,61

結(jié)論:

RUN2:1,3,14,15,27,30,48,52,63,89RUN3:4,13,24,33,46,58,76

11.5最正確歸并樹(shù)問(wèn)題:由置換-選擇生成所得的初始?xì)w并段，其各段長(zhǎng)度不等對(duì)平衡歸并有何影響？假設(shè)由置換-選擇得到9個(gè)初始?xì)w并段，其長(zhǎng)度(即記錄數(shù))依次為：9,30,12,18,3,17,2,6,24?，F(xiàn)作3-路平衡歸并，其歸

并樹(shù)如下圖：93012183172624

51

38

32

121

假設(shè)每個(gè)記錄占一個(gè)物理塊，則兩趟歸并所需對(duì)外存進(jìn)行的讀/寫(xiě)次數(shù)為(9+30+12+18+3+17+2+6+24)*2*2=484顯然，歸并方案不同，所得歸并樹(shù)亦不同，樹(shù)的帶權(quán)路徑長(zhǎng)度(或外存讀/寫(xiě)次數(shù))亦不同。回想在第六章中哈夫曼樹(shù)構(gòu)造方法。可得如下圖所示：3-路平衡歸并的最正確歸并樹(shù)(446次讀/寫(xiě))29311612171824

30