十章外部排序.ppt

《十章外部排序.ppt》由会员分享，可在线阅读，更多相关《十章外部排序.ppt（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、十章外部排序 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望本章内容本章内容p外存信息的存取p外部排序的基本方法归并排序法p多路平衡归并p置换-选择排序外部排序的应用对象保存在外存储器上的信息量很大的数据记录文件。外排序与内排序的差别p内部排序充分利用内存可以随机存取的特点，如n希尔排序中，相隔di的记录关键字可作比较；n堆排序中，完全二叉树中父Ri与子R2i，R2i+1可比n快速排序中，需正向和逆向访问记录序列p外存信息的定位和存取受其物理特性的限制外部排序的实

2、现手段在排序过程中，进行多次内外存之间的数据交换外部排序的特点外部排序的特点外排序基本方法：归并排序外排序基本方法：归并排序步骤步骤p生成若干初始归并串/顺串(文件预处理)n把含有把含有n个记录的文件，按内存缓冲区大小分成若干长度为个记录的文件，按内存缓冲区大小分成若干长度为L的子文件（段）；的子文件（段）；n分别调入内存用有效的内排序方法排序后送回外存；分别调入内存用有效的内排序方法排序后送回外存；p 多路合并n对初始归并串逐趟合并，直至最后在外存上得到整个有序文件为止对初始归并串逐趟合并，直至最后在外存上得到整个有序文件为止例例某文件共10000个记录，设每个物理块可以容纳200个记录，内

3、存缓冲区可以容纳5个物理块 1)经过10次内排序后得到10个初始归并段R1R10 2)采用两路归并，需四趟可以得到排好序的文件 R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 2000 2000 2000 2000 2000 4000 4000外排序总时间：8000 内排序：10tIS 10000 I/O操作：100tIO(排序)+(100+80+80+100)tIO(归并)=460tIO 归并：(10000+8000+8000+10000)tmg=46000 tmg提高外排序效率的途径提高外排序效率的途径 p扩大初始归并段长度，从而减少初始归并段个数mp进行多路(k路)归并减少

4、合并趟数减少合并趟数s，以减少，以减少I/O次数次数s=logkm多多 路路 归归 并并多路平衡归并多路平衡归并通过简单比较进行通过简单比较进行K路归并存在的问题路归并存在的问题 设记录总数为n，初始归并段的个数为m，从k个记录中选择一个关键字最小的记录时的比较次数为c则s趟内部归并总的比较次数为：C=sc(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无关矛盾1 2 k胜者树胜者树(树形选择排序树形

5、选择排序)6 8 6 8 9 8 9 6 8 90 9 15 8 90 10 9 20 6 8 12 10 9 20 15 8 12 10 9 20 6 8 12 90 10 9 20 15 8 12 90 14 22 24 15 16 17 92 14 22 24 25 16 17 92 26 38 30 25 50 18 97 26 38 30 50 18 97 7路合并胜者树路合并胜者树 重构后的胜者树重构后的胜者树 重构胜者树时，从根结点至新补入记录的叶结点的重构胜者树时，从根结点至新补入记录的叶结点的路径上的所有结点都必须更新。路径上的所有结点都必须更新。败者树败者树 5 2 2 0

6、 4 0 1 3 6 90 1 3 6 90 10 9 20 6 8 12 10 9 20 15 8 12 10 9 20 6 8 12 90 10 9 20 15 8 12 90 14 22 24 15 16 11 92 14 22 24 25 16 11 92 26 38 30 25 50 18 97 26 38 30 50 18 97 7路合并败者树 重构后的败者树败者树的特点：记录败者，胜者参加下一轮比赛 败者树的优点：重构时修改结点较少01 2 3 4 5 64ls05ls01 2 3 4 5 60 4 5 2 0 1 3 6 90 0 10 9 20 6 8 12 1 2 3 4

7、5 6调整败者树的方法:将新补充的结点与其双亲结点比较,败者留在该双亲结点,胜者继续向上直至树根的双亲以在b4补充15为例154与3比较4与2比较42与5比较25调整败者树的方法调整败者树的方法 7 7 7 7 7 7 7 90 0 10 9 20 6 8 12 1 2 3 4 5 6k-路归并对内存的要求路归并对内存的要求 至少要有k个输入缓冲区和一个输出缓冲区建败者树的过程7-1初始化败者树调整b66调整b55调整b44调整b334调整b22调整b1124调整b0054建败者树的过程建败者树的过程数据结构数据结构(依据：败者树为完全二叉树)p主：b0.k b0.k-1k个叶结点 ，存放k个

8、输入归并段中当前 参加归并的记录（缓冲区）bk虚拟记录，该关键字取可能的最小值minkeyp辅：ls0.k-1 不含叶结点的败者树 存放最后胜出的编号（ls0）以及所记录的败者编号处理步骤处理步骤p建败者树ls0.k-1p重复下列操作直至k路归并完毕n将将bls0写至输出归并段写至输出归并段n补充记录补充记录(某归并段变空时某归并段变空时,补补)，调整败者树，调整败者树多路平衡归并算法多路平衡归并算法算法描述：建立败者树算法描述：建立败者树void CreateLoserTree()bk=MINKEY;for(i=0;i=0;i+)Adjust(i);void Adjust(int s)for

9、(t=(s+k)/2;t 0;t/=2)if(bs blst)s lst;ls0=s;算法描述算法描述:K路合并路合并void K_Merge()for(i=0;i k;i+)input(i);/*第i路输入一个元素到bi*/CreateLoserTree(ls);while(bls0!=MAXKEY)q=ls0;output(bq);input(q);Adjust(q);置置 换换-选选 择择 排排 序序置换置换-选择排序选择排序目标目标 扩大初始归并段长度，突破内存工作区容量(设w个记录)的限制。置换置换-选择排序原理选择排序原理 内存 外存 原始文件 内存工作区 FI WA 初始归并段文

10、件 (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)示例示例 利用败者树利用败者树(教材教材303303页图页图

11、11.6)11.6)FO WA(4个记录)FI 空 空 36,21,33,87,23,7,62,16,54,43,29,空 36,21,33,87 23,7,62,16,54,43,29,21 36,23,33,87 7,62,16,54,43,29,21,23 36,7,33,87 62,16,54,43,29,21,23,33 36,7,62,87 16,54,43,29,21,23,33,36 16,7,62,87 54,43,29,21,23,33,36,62 16,7,54,87 43,29,21,23,33,36,62,87 16,7,54,43 29,21,23,33,36,62

12、,87|7 16,29,54,43 p处理步骤处理步骤 1)初始化败者树：1.1)所有外部结点：rnum=0;key=0；所有内部结点置0；1.2)对外部结点从编号w-1至0 从外存FI读入记录，置段号为1，并调整败者树 2)置当前段号为1；3)若ls0指示的外部结点属于当前段，输出该记录；否则,当前段号+1，输出段标后再输出该记录；4)若FI未空，从FI补充记录，若补充key此前输出记录的key，则rnum=当前段号+1 否则rnum=当前段号 否则补虚记录：key=;rnum=当前段号+1；5)调整败者树 转3）直至所有记录被输出调整败者树原则：段号小者为胜者段号相同，关键字小的为胜者置换

13、置换-选择排序的效果选择排序的效果p所得初始排序段的长度不等p当输入文件记录的关键字大小随机分布时，初始归并段的平均长度为内存工作区大小w的两倍最最 佳佳 归归 并并 树树最佳归并树最佳归并树文件经过置换文件经过置换-选择排序之后，得到长度不等的初始归并选择排序之后，得到长度不等的初始归并段，进行段，进行k路归并时，初始归并段的不同搭配，会导致路归并时，初始归并段的不同搭配，会导致归并过程中归并过程中I/O的次数的次数不同。不同。设有9个初始归并段，记录个数(长度)分别为：9，30，12，18，3，17，2，6，24 121 121 51 38 32 30 32 59 9 30 12 18 3

14、 17 2 6 24 11 9 12 17 18 24 2 3 6(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 2倍倍IO方案二方案一最佳归并树的构造最佳归并树的构造最佳归并树即k叉(阶)哈夫曼树。设初始归并段为m个，进行k-路归并1）若(m-1)mod(k-1)0 则需附加(k-1)-(m-1)mod(k-1)个长度为0的虚段，以使每次归并都可以对应k个段2）按照哈夫曼树的构造原则（权值越小的结点离根结点越远）构造

15、最佳归并树。k k阶哈夫曼树阶哈夫曼树示例示例 长度分别为2，3，6，9，12，17，18，24的8个初始归并段进行3路归并，求最佳归并树。91 20 24 47 5 6 9 12 17 18 0 2 3I/O次数：(2+3)3+(6+9+12+17+18)2+241 2 =326作业作业1.假设一次I/O的物理块可容纳150个记录，每次可对750个记录进行内部排序，那么对含有150000个记录的磁盘文件进行4-路平衡归并排序时，共需进行多少次I/O？2.已知某文件经过置换-选择排序之后，得到长度分别为47，9，31，18，4，12，23和7（单位均为物理块）的8个初始归并段。试为3-路平衡归并设计一个读写外存次数最少的归并方案，并求出读写外存的次数。3.在外排序中怎样减少排序的总时间？