1、31.07.2020，1，10章外部對齊、牙齒章節(jié)中的學(xué)習(xí)內(nèi)容、10.1外部對齊的基本概念、10.2多路復(fù)用集成實現(xiàn)、31.07.2020，2，10.1外部對齊的基本概念、內(nèi)部對齊直接位于計算機(jī)上，要對齊的數(shù)據(jù)可以一次加載到電腦內(nèi)存中。牙齒數(shù)據(jù)的對齊可以直接在內(nèi)存中執(zhí)行，因此使用以前的內(nèi)部對齊即可。要對齊的數(shù)據(jù)楊怡很多，不能一次安裝在內(nèi)存中，如果要將數(shù)據(jù)放入外部內(nèi)存(磁帶、磁盤)，則必須使用牙齒一章中介紹的外部對齊，因為內(nèi)部對齊不能滿足要求。外部對齊是使用內(nèi)存、外部內(nèi)存一起完成的。外部排序可以包含兩個單獨的步驟。首先，將可用內(nèi)存的大小、外部內(nèi)存中有N條記錄的文件劃分為M長度的子檔案或段，依次讀

2、取內(nèi)存，使用上一章的內(nèi)部排序方法(通常實現(xiàn)為堆排序)完成每個段的排序，然后將其存儲在外部內(nèi)存中。然后，合并牙齒段，使合并段從小到大逐漸增大，直到整個文件有序。第一步是上一章中介紹的內(nèi)部排序方法，因此牙齒章節(jié)主要介紹第二步的合并實現(xiàn)。第二階段合并有雙向平衡合并和多向平衡合并。下面首先舉例說明，具體的實施方法見以下部分。31.07.2020，3，假設(shè)有10，000條記錄的文件，一次只能加載1000條記錄，則可以將文件分成10個部分，每個部分包含1000條記錄。首先，通過10次內(nèi)部排序獲得10個初始合并段R1R10。每個段包含1000個唱片(有序)。然后，可以將其存儲在外部內(nèi)存中，然后使用雙向平衡積

3、分按順序創(chuàng)建整個文件。雙向平衡合并如圖10-1所示。圖10-1雙向平衡合并過程，31.07.2020，4，對于剛才的文檔，首先通過10次內(nèi)部排序獲得10個初始合并段R1R10。在牙齒過程中，每個段包含1000條記錄。然后，可以將其存儲在外部內(nèi)存中，然后利用5次平衡回歸。圖10-2 5方向平衡集成流程，31.07.2020，5，通常外部對齊所需的總時間=內(nèi)部對齊所需的時間(創(chuàng)建初始集成段)m*tIS外部內(nèi)存信息讀寫時間d*tIO平衡集成所需的時間S，M是初始集成段的數(shù)量，tIS是初始集成段的內(nèi)部d是讀和寫的總數(shù)，tIO是一次外部內(nèi)存讀和寫時間的平均值。s是合并數(shù)，utmg是內(nèi)部合并U個記錄所需的

4、時間。對于同一文檔，假定有M個初始合并段，K負(fù)載平衡合并，合并的行數(shù)可以表示為s=logkm。增加k或減少m可以減少s，減少外部對齊所需的總時間。31.07.2020，6，10.2多路復(fù)用集成實施，創(chuàng)建10.2.1初始集成段，初始等待文件為輸入檔案FI，初始合并段文件為輸出檔案FO，內(nèi)存工作區(qū)為WA、FO和WA的初始狀態(tài)為空，(2)在WA中選擇關(guān)鍵字最小的記錄，并將其記錄為MINKEY。(3)將MINKEY記錄輸出為FO。(4)如果FI不為空，請輸入從FI到WA的以下記錄：(5)在WA中，選擇所有大于MINKEY的關(guān)鍵字中最小的關(guān)鍵字作為新MINKEY。(6)在WA中，重復(fù)(3)(5)直到無法

5、選擇新的MINKEY，以獲得初始合并段。(7)重復(fù)(2)(6)，直到WA為空。獲取所有初始合并段。例如，給定的初始文件包含24條記錄，每條記錄包含關(guān)鍵字51，49，39，46，38，29，14，61，15，30，1，48，52，3。使用上述方法創(chuàng)建初始合并段的過程如下表所示，31.07.2020，7，表10-1創(chuàng)建初始合并段，31.07.2020，8，表10-1創(chuàng)建初始合并段(繼續(xù))，31.07.2020 39，46，49，51，61第二個合并段R1: 1，3，現(xiàn)在以五向平衡集成為例，創(chuàng)建了“敗者樹”。假定通過上一方法(此處指示段的結(jié)束)獲得了五個初始合并段：第一個合并段B0: 17，21，第

6、二個合并段B4:15: 05，44，“失敗樹”實施中，以完整二叉樹格式從每個初始合并段中獲取關(guān)鍵字B3和B4比較，B3是失敗者，其段號存儲在Ls4中，B3和B4的勝者再與B0比較，敗者將B0，其段號存儲在Ls2中，B1和B2比較，敗者的段號存儲在Ls3中，B0，B1，B2，B2，B2多重均衡合并的實現(xiàn)，多重均衡合并的實現(xiàn)，就是反復(fù)調(diào)整輸家樹，輸出Ls0的值，直到樹中葉節(jié)點全部顯示出來?，F(xiàn)在舉例說明五向平衡合并。范例10-1假設(shè)有5個初始合并節(jié)段(此處指示節(jié)段的結(jié)束):第一個合并節(jié)段B0: 17，21，第二個合并節(jié)段B4:15: 05，44，第三個合并節(jié)段B3:29: 10，具體實施過程如圖10

7、-4所示。，(a)生成的初始輸家樹，(b)輸出05后的輸家樹，(c)輸出05，10后的輸家樹，(d)輸出05，10，15，17，21后的輸家樹，(d)輸出05，10，15，17，21后的輸家樹多路復(fù)用集成算法實現(xiàn)，# include # /失敗樹中非葉節(jié)點的存儲空間int bk 1；/失敗樹的葉節(jié)點存儲空間，void adjust (intlsk，ints)int=(s k)/2；Int tempwhile(t0)if(bs blst)temp=s；S=lstLst=tempt=t/2；ls0=s；31.07.2020，19，為void createlosttree (intlsk)/創(chuàng)建失敗者樹(int I=0；I=0；-I)曹征(ls，I)；void k_merge(int lsk，int bk) /K公路平衡合并f