外部排序

第十章外部排序本章内容外存信息的存取外部排序的基本方法—归并排序法多路平衡归并置换-选择排序外部排序的应用对象保存在外存储器上的信息量很大的数据记录文件。外排序与内排序的差别内部排序充分利用内存可以随机存取的特点，如希尔排序中，相隔di的记录关键字可作比较；堆排序中，完全二叉树中父R[i]与子R[2i]，R[2i+1]可比快速排序中，需正向和逆向访问记录序列外存信息的定位和存取受其物理特性的限制外部排序的实现手段在排序过程中，进行多次内外存之间的数据交换外部排序的特点外排序基本方法：归并排序[步骤]生成若干初始归并串/顺串(文件预处理)把含有n个记录的文件，按内存缓冲区大小分成若干长度为L的子文件（段）；分别调入内存用有效的内排序方法排序后送回外存；多路合并对初始归并串逐趟合并，直至最后在外存上得到整个有序文件为止[例]某文件共10000个记录，设每个物理块可以容纳200个记录，内存缓冲区可以容纳5个物理块1)经过10次内排序后得到10个初始归并段R1~R102)采用两路归并，需四趟可以得到排好序的文件R1R2R3R4R5R6R7R8R9R102000200020002000200040004000外排序总时间：8000内排序：10tIS10000I/O操作：100tIO(排序)+(100+80+80+100)tIO(归并)=460tIO归并：(10000+8000+8000+10000)tmg=46000tmg提高外排序效率的途径扩大初始归并段长度，从而减少初始归并段个数m进行多路(k路)归并减少合并趟数s，以减少I/O次数s=logkm多路归并多路平衡归并[通过简单比较进行K路归并存在的问题]设记录总数为n，初始归并段的个数为m，从k个记录中选择一个关键字最小的记录时的比较次数为c则s趟内部归并总的比较次数为：C=sc(n-1)=logkmc(n-1)=log2m/log2kc(n-1)k，s，可减少I/O次数；k，c=(k-1)，归并效率[解决矛盾的方法]——利用“败者树”选关键字最小的记录此时c=log2k则C=log2m(n-1)，与k无关矛盾…12……k胜者树(树形选择排序)686898968909158901092068121092015812109206812901092015812901422241516179214222425161792263830255018972638305018977路合并胜者树重构后的胜者树重构胜者树时，从根结点至新补入记录的叶结点的路径上的所有结点都必须更新。败者树52204013690136901092068121092015812109206812901092015812901422241516119214222425161192263830255018972638305018977路合并败者树重构后的败者树败者树的特点：记录败者，胜者参加下一轮比赛败者树的优点：重构时修改结点较少01234564ls[0]5ls[0]12345604520136900109206812123456调整败者树的方法:将新补充的结点与其双亲结点比较,败者留在该双亲结点,胜者继续向上直至树根的双亲以在b[4]补充15为例154与3比较4与2比较42与5比较25调整败者树的方法7777777900109206812123456[k-路归并对内存的要求]至少要有k个输入缓冲区和一个输出缓冲区建败者树的过程7-1初始化败者树调整b[6]6调整b[5]5调整b[4]4调整b[3]34调整b[2]2调整b[1]124调整b[0]054建败者树的过程[数据结构](依据：败者树为完全二叉树)主：b[0..k]b[0..k-1]——k个叶结点，存放k个输入归并段中当前参加归并的记录（缓冲区）b[k]——虚拟记录，该关键字取可能的最小值minkey辅：ls[0..k-1]——不含叶结点的败者树存放最后胜出的编号（ls[0]）以及所记录的败者编号[处理步骤]建败者树ls[0..k-1]重复下列操作直至k路归并完毕将b[ls[0]]写至输出归并段补充记录(某归并段变空时,补)，调整败者树多路平衡归并算法算法描述：建立败者树voidCreateLoserTree(){b[k]=MINKEY;for(i=0;ik;i++)ls[i]=k;for(i=k-1;i=0;i++)Adjust(i);}voidAdjust(ints){for(t=(s+k)/2;t0;t/=2){if(b[s]b[ls[t]])sls[t];}ls[0]=s;}算法描述:K路合并voidK_Merge(){for(i=0;ik;i++)input(i);/*第i路输入一个元素到b[i]*/CreateLoserTree(ls);while(b[ls[0]]!=MAXKEY){q=ls[0];output(b[q]);input(q);Adjust(q);}}置换-选择排序置换-选择排序[目标]扩大初始归并段长度，突破内存工作区容量(设w个记录)的限制。[置换-选择排序原理]内存外存原始文件内存工作区FIWA初始归并段文件(w个记录)FO为简化问题，设每个物理块存放一个记录1)从FI输入w个记录到工作区WA；2)在FO中标记一个归并段开始；3)从WA中选出最小关键字记录，记为minimax记录；4)将minimax记录输出到FO中；5)从FI输入下一个记录到WA中；6)在WA中的关键字比minimax大的记录中选出关键字最小的记录6.1)若不能选到，在FO中标记一个归并段结束；若由于WA为空而未选出，则结束处理；否则，标记下一个归并段开始，转3)6.2)否则，将选出的记录作为新的minimax记录，转4)[示例]利用败者树(教材303页图11.6)FOWA(4个记录)FI空空36,21,33,87,23,7,62,16,54,43,29,…空36,21,33,8723,7,62,16,54,43,29,…2136,23,33,877,62,16,54,43,29,…21,2336,7,33,8762,16,54,43,29,…21,23,3336,7,62,8716,54,43,29,…21,23,33,3616,7,62,8754,43,29,…21,23,33,36,6216,7,54,8743,29,…21,23,33,36,62,8716,7,54,4329,…21,23,33,36,62,87||716,29,54,43……处理步骤1)初始化败者树：1.1)所有外部结点：rnum=0;key=0；所有内部结点置0；1.2)对外部结点从编号w-1至0从外存FI读入记录，置段号为1，并调整败者树2)置当前段号为1；3)若ls[0]指示的外部结点属于当前段，输出该记录；否则,当前段号+1，输出段标后再输出该记录；4)若FI未空，从FI补充记录，若补充key此前输出记录的key，则rnum=当前段号+1否则rnum=当前段号否则补虚记录：key=;rnum=当前段号+1；5)调整败者树转3）直至所有记录被输出调整败者树原则：段号小者为胜者段号相同，关键字小的为胜者置换-选择排序的效果所得初始排序段的长度不等当输入文件记录的关键字大小随机分布时，初始归并段的平均长度为内存工作区大小w的两倍最佳归并树最佳归并树文件经过置换-选择排序之后，得到长度不等的初始归并段，进行k路归并时，初始归并段的不同搭配，会导致归并过程中I/O的次数不同。设有9个初始归并段，记录个数(长度)分别为：9，30，12，18，3，17，2，6，241211215138323032599301218317262411912171824236(9+30+12+18+3+17+2+6+24)2[(2+3+6)3+(9+12+17+(51+38+32)2+18+24)2+301]2=484=4463-路归并所有叶结点加权外通路长度的2倍IO方案二方案一最佳归并树的构造最佳归并树即k叉(阶)哈夫曼树。设初始归并段为m个，进行k-路归并1）若(m-1)mod(k-1)0则需附加(k-1)-(m-1)mod(k-1)个长度为0的虚段，以使每次归并都可以对应k个段2）按照哈夫曼树的构造原则（权值越小的结点离根结点越远）构造最佳归并树。k阶哈夫曼树示例长度分别为2，3，6，9，12，17，18，24的8个初始归并段进行3路归并，求最佳归并树。91202447569121718023I/O次数：[(2+3)3+(6+9+12+17+18)2+241]2=326作业1.假设一次I/O的物理块可容纳150个记录，每次可对750个记录进行内部排序，那么对含有150000个记录的磁盘文件进行4-路平衡归并排序时，共需进行多少次I/O？2.已知某文件经过置换-选择排序之后，得到长度分别为47，9，31，18，4，12，23和7（单位均为物理块）的8个初始归并段。试为3-路平衡归并设计一个读写外存次数最少的归并方案，并求出读写外存的次数。3.在外排序中怎样减少排序的总时间？