數(shù)據(jù)結(jié)構(gòu)與算法：第7章 外部分類(lèi)

7.1磁盤(pán)文件的歸并分類(lèi)7.2磁帶文件的歸并分類(lèi)第7章外部分類(lèi)歸并方法：首先將文件中的數(shù)據(jù)輸入到內(nèi)存，采用內(nèi)部分類(lèi)方法進(jìn)行分類(lèi)（歸并段），然后將有序段寫(xiě)回外存；對(duì)多歸并段進(jìn)行多遍歸并，最后形成一個(gè)有序序列。7.1磁盤(pán)文件的歸并分類(lèi)磁盤(pán)信息的存取

磁盤(pán)：是一個(gè)扁平的圓盤(pán)，盤(pán)面上有許多稱(chēng)為磁道的圓圈，信息就記載在磁道上。它是一種直接存取的存儲(chǔ)設(shè)備（DASD）。

磁盤(pán)的工作原理：盤(pán)片裝在一個(gè)主軸上，并繞主軸高速旋轉(zhuǎn)，當(dāng)磁道在讀/寫(xiě)頭下通過(guò)時(shí)，便可進(jìn)行信息的讀/寫(xiě)。讀/寫(xiě)信息的功能由磁盤(pán)驅(qū)動(dòng)器執(zhí)行。

固定頭盤(pán)：固定頭盤(pán)的每一磁道上都有獨(dú)立的磁頭，這些磁頭固定不動(dòng)，專(zhuān)負(fù)責(zé)讀/寫(xiě)某一磁道上的信息。

活動(dòng)頭盤(pán)：活動(dòng)頭盤(pán)的磁頭是可以移動(dòng)的。一個(gè)盤(pán)面上只有一個(gè)磁頭，磁頭裝在一個(gè)動(dòng)臂上，可以從該面上的一道移動(dòng)到另一道。

在磁盤(pán)上表明一個(gè)具體信息必須用一個(gè)三維地址：柱面號(hào)（確定讀/寫(xiě)頭的徑向運(yùn)動(dòng))、盤(pán)面號(hào)、塊號(hào)(確定信息在盤(pán)片圓圈上的位置）。磁盤(pán)結(jié)構(gòu)：由磁盤(pán)驅(qū)動(dòng)器、讀、寫(xiě)磁頭、活動(dòng)臂、盤(pán)片（磁道、扇區(qū)）、旋轉(zhuǎn)主軸構(gòu)成。速度快、容量大、直接存取設(shè)備。訪(fǎng)問(wèn)一塊信息：（1）找柱面,移動(dòng)臂使磁頭移動(dòng)到所需柱面上(稱(chēng)為定位或?qū)げ?；（2）等待要訪(fǎng)問(wèn)的信息轉(zhuǎn)動(dòng)磁頭之下；（3）讀/寫(xiě)所需信息。磁盤(pán)上讀寫(xiě)一塊信息所需的時(shí)間為：

TI/O=tseek+tla+n*twm其中：tseek為尋查時(shí)間（seektime）：即讀/寫(xiě)頭定位的時(shí)間；

tla為等待時(shí)間（latencytime）：即等待信息塊的初始位置旋到讀/寫(xiě)頭下的時(shí)間；

twm為傳輸時(shí)間（transmissiontime）。例：假設(shè)一個(gè)磁盤(pán)文件，由4500個(gè)記錄組成，分別記為A1,A2,……,A4500

設(shè)系統(tǒng)提供容納750個(gè)記錄的內(nèi)存共分類(lèi)使用，每次磁盤(pán)讀寫(xiě)250個(gè)記錄的數(shù)據(jù)塊，則可設(shè)計(jì)分類(lèi)過(guò)程如下：(1)每次從文件中輸入三個(gè)數(shù)據(jù)塊（750個(gè)記錄）到工作空間，進(jìn)行內(nèi)部分類(lèi)。分類(lèi)結(jié)果寫(xiě)回磁盤(pán)，構(gòu)成6個(gè)初始?xì)w并段：R1,R2,R3,R4,R5,R6R1R2R3R4R5R61-750751-15001501-22502251-30003001-37503751-4500（2）將內(nèi)存空間三等分，每塊250個(gè)記錄，其中2塊為輸入緩沖區(qū)，1塊為輸出緩沖區(qū)。歸并R1和R2，輸出到輸出緩沖區(qū)，若輸出緩沖區(qū)滿(mǎn)，則寫(xiě)盤(pán)。同樣，若

R1和R2的緩沖區(qū)出現(xiàn)空，則繼續(xù)讀盤(pán)，直到歸并結(jié)束為止。R12=R1+R2；同樣得到：R34=R3+R4,R56=R5+R6；

R12、R34、R56分別都包含1500個(gè)記錄。（3）類(lèi)似（2）的方法，可將R12和R34歸并成R1234,，再將R1234和R56進(jìn)行歸并。得到最后的排序結(jié)果。R1R2R3R4R5R6R12R34R56R1234R12346×750記錄3×1500記錄12×250記錄18×250記錄K路歸并……...遍數(shù)[log2m]層數(shù)[log2m]+1M個(gè)歸并段的歸并過(guò)程R1R2Rm-1Rm2…KK+1…2K……m...logkm+1levers(1)多路歸并——減少歸并遍數(shù)并行操作的緩沖區(qū)處理——使輸入、輸出和CPU處理盡可能重疊(3)初始?xì)w并段的生成討論問(wèn)題logkm遍比較次數(shù)：擴(kuò)大初始?xì)w并段長(zhǎng)度，從而減少初始?xì)w并段個(gè)數(shù)m進(jìn)行多路(k路)歸并減少合并趟數(shù)s，以減少I(mǎi)/O次數(shù)

s=logkm提高外排序效率的途徑(1)多路歸并——減少歸并遍數(shù)m個(gè)初始段進(jìn)行2路歸并，需要log2m遍歸并;一般地，m個(gè)初始段，采用k路歸并，需要logkm遍歸并。顯然，k越大，歸并遍數(shù)越少，可提高歸并的效率。

在k路歸并時(shí)，從k個(gè)關(guān)鍵字中選擇最小記錄時(shí)，要比較K-1次。若記錄總數(shù)為n，每遍要比較的次數(shù)為：

n*(k-1)[log2m/log2k]可以看出，隨著k增大，(k-1)/log2k也增大，當(dāng)歸并路數(shù)多時(shí)，CPU處理的時(shí)間也隨之增多。為此要選擇好的分類(lèi)方法，以減少分類(lèi)中比較次數(shù)。610920689901796817681516203820301525155011161001101820

選擇樹(shù)(Selectiontree)或敗者樹(shù)(treeofloser)分析：第一次建立選擇樹(shù)的比較所花時(shí)間為:O(k-1)=O(k)而后每次重新建造選擇樹(shù)所需時(shí)間為：

O(log2k)n個(gè)記錄處理時(shí)間為初始建立選擇樹(shù)的時(shí)間加上n-1次重新選擇樹(shù)的時(shí)間：

O((n-1)·

log2k)+O(k)=O(n·

log2k)這就是k路歸并一遍所需的CPU處理時(shí)間。歸并遍數(shù)為logkm，總時(shí)間為：

O(n·

log2k·

logkm)=O(n·

log2m)(k路歸并CPU時(shí)間與k無(wú)關(guān))最佳歸并樹(shù)

將哈夫曼樹(shù)進(jìn)行拓展，不僅對(duì)2叉樹(shù)，同樣可形成3叉、4叉、…、k叉樹(shù)，亦稱(chēng)為哈夫曼樹(shù)，同樣可求得帶權(quán)路徑長(zhǎng)度最小。最佳歸并樹(shù)：對(duì)長(zhǎng)度不等的m個(gè)初始?xì)w并段，構(gòu)造哈夫曼樹(shù)作為歸并樹(shù)，便可使在進(jìn)行外部歸并時(shí)所需要對(duì)外存進(jìn)行的讀寫(xiě)次數(shù)達(dá)到最小。

最佳歸并樹(shù)中，并不只是只有度為k和0的結(jié)點(diǎn)，會(huì)有缺額。當(dāng)初始?xì)w并段的數(shù)目不足時(shí)，需附加長(zhǎng)度為0的虛段，按照哈夫曼樹(shù)的構(gòu)造原則，權(quán)為0的葉子結(jié)點(diǎn)應(yīng)離樹(shù)根最遠(yuǎn)。問(wèn)題：起因：由于初始?xì)w并段通常不等長(zhǎng),進(jìn)行歸并時(shí),長(zhǎng)度不同的初始?xì)w并段歸并的順序不同,讀寫(xiě)外存的總次數(shù)也不同。目的：減少讀寫(xiě)外存的次數(shù)。

例：假定由置換－選擇分類(lèi)法生成了9個(gè)初始?xì)w并段，記錄數(shù)分別為9、30、12、18、3、17、2、6、24。如果進(jìn)行3-路歸并，請(qǐng)討論在各種情況下的對(duì)外存的讀寫(xiě)次數(shù)。從外存讀121個(gè)記錄寫(xiě)入外存121個(gè)記錄從外存讀121個(gè)記錄寫(xiě)入外存121個(gè)記錄30129317186242513832121總共讀寫(xiě)外存484個(gè)記錄從外存讀11個(gè)記錄寫(xiě)入外存11個(gè)記錄從外存讀91個(gè)記錄寫(xiě)入外存121個(gè)記錄寫(xiě)入外存91個(gè)記錄從外存讀121個(gè)記錄62392417183011325912112總共讀寫(xiě)外存446個(gè)記錄按照hafuman樹(shù)的思想，記錄少的段最先合并。不夠時(shí)增加虛段。從外存讀5個(gè)記錄寫(xiě)入外存67個(gè)記錄從外存讀91個(gè)記錄寫(xiě)入外存67個(gè)記錄寫(xiě)入外存91個(gè)記錄32691718125204791總共讀寫(xiě)外存326個(gè)記錄24從外存讀5個(gè)記錄

虛段的補(bǔ)法:

在K路平衡歸并時(shí)，它的歸并樹(shù)的模型是一棵度為K的樹(shù)。在這棵樹(shù)上的結(jié)點(diǎn)要么是葉子，要么是具有K個(gè)孩子的內(nèi)部結(jié)點(diǎn)。設(shè)具有K個(gè)孩子的內(nèi)部結(jié)點(diǎn)共有nk

個(gè)。初始?xì)w并段的個(gè)數(shù)為m個(gè)。設(shè)n=nk+m，故：從結(jié)點(diǎn)出發(fā)的分枝，共計(jì)有K*nk

個(gè)。若從進(jìn)入結(jié)點(diǎn)的角度進(jìn)行考慮，則共有：nk+m-1注意：沒(méi)有分枝進(jìn)入根結(jié)點(diǎn)。所以，K*nk＝nk+m-1

于是：nk=(m-1)/(K-1)

這就意味著，若(m-1)MOD(K-1)＝0，無(wú)需增加虛段。否則，要增加虛段，其數(shù)目為：

（K-1)-(m-1)MOD(K-1)限制：由于磁帶尋找具有最少記錄的初始?xì)w并段，必須反復(fù)倒帶。所以，實(shí)用性不強(qiáng)。在磁盤(pán)的情況下，需要有段包含的記錄數(shù)信息、段的位置信息等。文件如集中放置在幾個(gè)相鄰的柱面上的情況比較合適。并行操作的緩沖區(qū)處理——使輸入、輸出和CPU處理盡可能重疊----1324ou(1)ou(2)iu(1)iu(2)----iu(3)iu(4)12---3-457--34----57615歸并到ou(1)輸入到in(3)歸并到ou(2)輸入到in(4)輸出ou(1)(a)(b)(c)56

89---7-15

78-92025---159-

--2025

-15歸并到ou(1)輸入到in(1)歸并到ou(1)輸入到in(3)輸出ou(2)(d)(e)(f)歸并到ou(2)輸入到in(2)輸出ou(1)輸出ou(2)

對(duì)k個(gè)歸并段進(jìn)行k路歸并至少需要k個(gè)輸入和1個(gè)輸出緩沖區(qū)，要使輸入、輸出和歸并同時(shí)進(jìn)行，k+1個(gè)緩沖區(qū)是不夠的，需要2k個(gè)輸入緩沖區(qū)實(shí)現(xiàn)并行操作。135789246152025(3)初始?xì)w并段的生成步12345678910111213…緩沖區(qū)內(nèi)容151515(11)(11)(11)(11)(11)(11)1111(06)……1919191925(16)(16)(16)(16)161616……04122727272734(26)(26)262626……8383838383838383(07)109090……輸出結(jié)果0412151925273483

07101116…R1R2(a)初始?xì)w并段的長(zhǎng)度≥緩沖區(qū)的長(zhǎng)度(b)任何內(nèi)部分類(lèi)算法都可作為生成初始?xì)w并段的算法(c)例如：緩沖區(qū)的長(zhǎng)度為4，輸入序列為：

151904831227112516342607109006…新輸入記錄.key小于當(dāng)前記錄.key，等待下一個(gè)歸并段采用選擇樹(shù)法生成初始?xì)w并段的長(zhǎng)度平均是緩沖區(qū)長(zhǎng)度的兩倍。7.2磁帶文件的歸并分類(lèi)（外部）存儲(chǔ)設(shè)備——紙帶、磁鼓、磁帶、磁盤(pán)等磁帶信息的表示：一種磁化方向、代表1另一種磁化方向，代表00100100110101111關(guān)于磁帶==〉磁帶信息的存取

磁帶：一條薄薄涂上一層磁性材料的窄帶（現(xiàn)在使用的磁帶大多數(shù)有1/2英寸寬，最長(zhǎng)可達(dá)3600英尺，繞在一個(gè)卷盤(pán)上）。它是一種順序存取的存儲(chǔ)設(shè)備。

磁帶的工作原理：使用時(shí)，將磁帶放在磁帶機(jī)上，驅(qū)動(dòng)器控制磁帶盤(pán)轉(zhuǎn)動(dòng)，帶動(dòng)磁帶向前移動(dòng)。通過(guò)讀/寫(xiě)頭就可以讀出磁帶上的信息或者把信息寫(xiě)入磁帶中。

7道帶：在1/2英寸寬的帶面上記錄7位二進(jìn)制信息的磁帶。

9道帶：在1/2英寸寬的帶面上記錄9位二進(jìn)制信息的磁帶。每一橫排可表示一個(gè)字符（8位表示一個(gè)字符，剩下的一位作奇偶校驗(yàn)位）。

信息密度：每英寸的二進(jìn)制字符數(shù)。通常為每英寸800位或1600位或6250位。移動(dòng)速度：每秒200英寸。

間隙IRG（InterRecordGap）：磁帶上相鄰兩組字符組（記錄）之間的空白區(qū)。根據(jù)啟停時(shí)間的需要，這個(gè)間隙通常為1/4~3/4英寸。

例如，若每個(gè)字符組的長(zhǎng)度是80個(gè)字符，IRG為3/4英寸，則對(duì)密度為每英寸1600個(gè)字符的磁帶，其利用率僅為1/16，有15/16的帶用于IRG。如圖11.1(a)所示。

塊間間隙IBG（InterBlockGap）：將若干個(gè)字符組合并成塊，每個(gè)字符組間沒(méi)有IRG，而變成塊間的間隙。

例如，圖(b)表示將20個(gè)長(zhǎng)度為80字符的字符組存放在磁帶上的一個(gè)物理塊中的情況。IRGIRGIRG記錄(a)字符組長(zhǎng)80字符的磁帶IBGIBGIBG20個(gè)記錄20個(gè)記錄20個(gè)記錄(b)成塊存放的磁帶磁帶上信息存放示意圖磁帶上讀寫(xiě)一塊信息所需的時(shí)間為： TI/O=ta+n*tw其中：ta為延遲時(shí)間，讀/寫(xiě)頭到達(dá)傳輸信息所在物理塊起始位置所需時(shí)間（顯然，延遲時(shí)間和信息在磁帶上的位置、當(dāng)前讀/寫(xiě)頭所在位置有關(guān)）；tw為傳輸一個(gè)字符的時(shí)間。成塊的優(yōu)點(diǎn)：（1）可以減少I(mǎi)RG的數(shù)目，從而提高磁帶的利用率，塊的長(zhǎng)度大于IBG的長(zhǎng)度。（2）可以減少I(mǎi)/O操作。因?yàn)橐淮蜪/O操作可把整個(gè)物理塊都讀到內(nèi)存緩沖區(qū)中，然后再?gòu)木彌_區(qū)中取出所需要的信息（一個(gè)字符組）。每當(dāng)要讀一個(gè)字符組時(shí)，首先要查緩沖區(qū)中是否已有，若有，則不必執(zhí)行I/O操作，直接從緩沖區(qū)讀取即可。

與磁盤(pán)不同，磁帶是順序存儲(chǔ)設(shè)備，讀取信息塊的時(shí)間與信息塊的位置有關(guān)。研究磁帶分類(lèi)，需要了解信息塊的分布。K路平衡歸并分類(lèi)磁帶機(jī)數(shù)量：2k輸入：T1,T2,……,Tk

輸出輸出：Tk+1,Tk+2,……,T2k

輸入磁帶機(jī)T1T2…Tk歸并段R1R2…RkRk+1Rk+2…R2k…………Rmk+1………T1:R1(1000),R3(1000),R5(1000)T2:R2(1000),R4(1000),R6(1000)T3:?T4:?T1:?T2:?T3:

R1(2000),R3(2000)T4:R2(2000)T1:R1(4000)T2:

R2(2000)T3:?T4:?T1:?T2:?T3:R1(6000)

T4:?i遍后t1t2t3開(kāi)始13(1L)21(L)空1空8(1L)13(2L)28(3L)空5(2L)33(3L)5(5L)空4空2(5L)3(8L)52(13L)空1(8L)61(13L)1(21L)空7空空1(34L)步t1t2t3總段數(shù)n0011n-11102n-22013n-30235n-43508n-580513n-6081321n-71321034多階段歸并分類(lèi)

K+1臺(tái)磁帶機(jī)，實(shí)現(xiàn)k路歸并K階Fibonacci數(shù)列tji表示第j步中邏輯上第i臺(tái)磁帶機(jī)。n-j步歸并段分布規(guī)則空磁帶機(jī)臺(tái)號(hào)=K+1當(dāng)j=0或k+1的整數(shù)倍j%(k+1)j不為上述值注：在多路歸并中，若要求歸并的文件其初始?xì)w并段總數(shù)不是K階Fibonacci數(shù)，則需附加一些虛的歸并段數(shù)，以湊成k階Fibonacci數(shù)，同時(shí)還應(yīng)該將虛歸并段適當(dāng)?shù)胤植荚趉路歸并的k臺(tái)磁帶上。例1：設(shè)有磁盤(pán)文件中記錄的關(guān)鍵字分別為：

10,20,15,25,12,13,21,30,8,16,10

用置換-選擇排序法產(chǎn)生初始?xì)w并段，問(wèn)可產(chǎn)生幾個(gè)初始?xì)w并段？每個(gè)初始?xì)w并段包含哪些記錄（設(shè)工作區(qū)能容納4個(gè)記錄）。解：內(nèi)存緩沖區(qū)可容納4個(gè)記錄，采用4路歸并的置換-選擇排序方法生成初始?xì)w并段，如表所示。步1234567891011緩沖區(qū)內(nèi)容101213212121(16)(16)16162020202020(8)(8)(8)151515153030303025252525252525(10)10輸出結(jié)果101213152021253081016

生成的第一個(gè)初始?xì)w并段第二個(gè)初始?xì)w并段例2：給出一組關(guān)鍵字T=(12,2,16,30,8,28,4,10,20,6,18),設(shè)內(nèi)存工作區(qū)可容納4個(gè)記錄，寫(xiě)出用置換-選擇排序得到的全部初始?xì)w并段。解：初始?xì)w并段1：2,8,12,16,28,30

初始?xì)w并段2：4,6,10,18,20例3：設(shè)有13個(gè)初始?xì)w并段，其長(zhǎng)度分別為：28,16,37,42,5,9,13,14,20,17,30,12,18。試畫(huà)出4路歸并時(shí)的最佳排序樹(shù)，并計(jì)算它的帶權(quán)路徑長(zhǎng)度。解：n=13,k=4

因?yàn)?n-1)%(k-1)=0,所以不需要加虛段。WPS=(5+9+12+13+14+16+17+18+20+28+30+37)×2+42=4805912131416171820283037651154226139最佳歸并樹(shù)例：假設(shè)4個(gè)初始?xì)w并段如下：

R1:15,16,25,32R2:3,22,28,45R3:1,12,30,42R4:33,60給出進(jìn)行4路歸并的過(guò)程。(1)輸出1R1:15,16,25,32R2:3,22,28,45R3:12,30,42R4:33,60(2)輸出1,3R1:15,16,25,32R2:22,28,45R3:12,30,42R4:33,60(3)輸出1,3,12R1:15,16,25,32R2:22,28,45R3:30,42R4:33,60(4)輸出1,3,12,15R1:16,25,32R2:22,28,45R3:30,42R4:33,60(5)輸出1,3,12,15,16R1:25,32R2:22,28,45R3:30,42R4:33,60(6)輸出1,3,12,15,16,22R1:25,32R2:28,45R3:30,42R4:33,60(7)輸出1,3,12,