第14周外排序第3讲-磁盘排序-多路平衡归并.pdf

《第14周外排序第3讲-磁盘排序-多路平衡归并.pdf》由会员分享，可在线阅读，更多相关《第14周外排序第3讲-磁盘排序-多路平衡归并.pdf（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、11.2.2 多路平衡归并多路平衡归并 1、 k路路平衡平衡归并概述归并概述 2路平衡归并：每一趟从路平衡归并：每一趟从m个归并段得到个归并段得到 m/2 个个归并段。归并段。 m8，k=2 例如：例如： log2m =3遍遍 什么是什么是k路平衡归并路平衡归并 一般地，一般地，2路平衡归并的前提：路平衡归并的前提：初始归并段的记录个数都相同。初始归并段的记录个数都相同。 可以推广到可以推广到k路路平衡归并平衡归并 归并时需要归并时需要读写磁盘的次数读写磁盘的次数 归并时需要关键字比较的次数归并时需要关键字比较的次数。 影响影响k路平衡归并的效率路平衡归并的效率 的的因素：因素： 影响影响k路

2、平衡归并的因素路平衡归并的因素 m8，假设每个归并段，假设每个归并段4个记录：个记录：k=2 读读记录次数记录次数 = WPL = 8 4 3 = 96 （如果每个记录占用一个物理块，（如果每个记录占用一个物理块，读写磁盘次数读写磁盘次数=96 2=192次次） 例如例如 k路平衡归并时读写磁盘次数的计算路平衡归并时读写磁盘次数的计算 采用采用k路平衡归并时，通常路平衡归并时，通常k越大，读写磁盘次数越大，读写磁盘次数会减少会减少。 采用采用k路平衡归并时路平衡归并时，则相应的归并树有则相应的归并树有 logkm +1层层，要对数据进行要对数据进行 logkm 趟扫描趟扫描。 m8 k2 lo

3、gkm 趟趟=3 k路平衡归并时关键字比较次数的计算路平衡归并时关键字比较次数的计算 logkm (u- -1) (k- -1) = log2m / log2k (u- -1) (k- -1) = log2m (u- -1) (k- -1) log2k u个记录个记录 logkm 趟趟 每一每一趟需趟需(u- -1)(k- -1)次次 关键字比较关键字比较 总共需要的总共需要的关键字比较次数关键字比较次数为：为： 总共总共需要的关键字比较次数需要的关键字比较次数： 结论：结论：增大增大归并路数归并路数k，读写磁盘次数减少，而关键字比较次数会，读写磁盘次数减少，而关键字比较次数会 增大。若增大。

4、若k增大到一定的程度，就会抵消掉由于减少读写磁盘次数而赢增大到一定的程度，就会抵消掉由于减少读写磁盘次数而赢 得的时间。得的时间。 log2m (u- -1) (k- -1) log2k 在初始归并段个数在初始归并段个数m与记录与记录个数个数u确定时确定时是常量是常量 (k- -1) log2k 在在k增大时会增大增大时会增大 利用利用败者树实现败者树实现k路平衡归并的路平衡归并的过程过程是：是： 2、 利用利用败者树实现败者树实现k路平衡归并过程路平衡归并过程 败者树败者树用于用于在在k个记录中选取最小关键字的记录个记录中选取最小关键字的记录。败者树类。败者树类 似于堆排序中的似于堆排序中的

5、堆堆。 先建立败者树。先建立败者树。 然后对然后对k个输入有序段进行个输入有序段进行k路平衡归并。路平衡归并。 【例例11- -2】 设有设有5个初始归并段，它们中各记录的关键字分别是：个初始归并段，它们中各记录的关键字分别是： F0：17，21， F1：5，44， F2：10，12， F3：29，32， F4：15，56， 其中其中，是段结束标志。说明利用败者树进行是段结束标志。说明利用败者树进行k=5路平衡归并排序路平衡归并排序 的过程。的过程。 构建败者树构建败者树 29 F3 15 F4 17 F0 5 F1 10 F2 5(-) 5(-) 5(-) 5(-) 冠军（最小者）冠军（最小

6、者） k=5：创建含有：创建含有k个叶子节点的完全二叉树，总共个叶子节点的完全二叉树，总共2k- -1=9个节点，另外添加一个节点，另外添加一 个冠军节点。个冠军节点。 每个叶子节点对应一个归并段，段号为每个叶子节点对应一个归并段，段号为04。 初始时每个初始时每个分支节点（含冠军节点）分支节点（含冠军节点）取值“取值“5(- )”，”，5表示段号（此时为虚拟表示段号（此时为虚拟 段号），段号），- 表示最小关键字。例如，某节点取值为“表示最小关键字。例如，某节点取值为“4(15)”，表示节点值来自”，表示节点值来自 4号段的关键字号段的关键字15对应的记录。对应的记录。 29 F3 15F4

7、 17 F0 5 F1 10 F2 冠军（最小者）冠军（最小者） 5(-) 5(-) 5(-) 5(-) 5(-) 4(15)3(29) 4(15)2(10) 1(5) 0(17) 4(15) 1(5) 败者树构建完毕败者树构建完毕 调整产生调整产生冠军（最小者）的过程冠军（最小者）的过程：从从F4F0操作：将当前节点的关键字与父节点操作：将当前节点的关键字与父节点 比较，将大的（比较，将大的（败者败者）放在父节点中，）放在父节点中，小者（胜者）继续进行，直到根节点。最后小者（胜者）继续进行，直到根节点。最后 将胜者放在将胜者放在冠军节点中。冠军节点中。 21 29F315F4 17F05F1

8、10F2 冠军（最小者）冠军（最小者） 5(-) 用败者树进行归并用败者树进行归并 5(-) 5(-) 5(-) 5(-) 4(15)3(29) 4(15)2(10) 1(5) 0(17) 4(15) 1(5) 44 12 15 32 归并文件：归并文件：5 1(44) 2(10) 10 依此进行，直到冠军为依此进行，直到冠军为才结束。才结束。 每次产生一个冠军，每次产生一个冠军，比较比较次数约为次数约为log2k。 logkm (u- -1) log2k = log2m (u- -1) log2k / log2k = log2m (u- -1) 利用利用败者树实现败者树实现k路平衡归并时，总

9、共需要的关键字比较次数为：路平衡归并时，总共需要的关键字比较次数为： 结论结论：关键字关键字比较次数与比较次数与k无关无关 总总的内部归并时间不会随的内部归并时间不会随k的增的增 大而大而增大增大。 只要内存空间允许，只要内存空间允许，尽可能增大归并路数尽可能增大归并路数k。 利用败者树实现利用败者树实现k路平衡归并路平衡归并 采用采用败者树，败者树，置换置换- -选择选择排序中关键字比较次数分析排序中关键字比较次数分析 共有共有n个记录，个记录，内存工作区内存工作区WA的容量为的容量为w： 若在若在w个记录中选取最小关键字的个记录中选取最小关键字的采用败者树方法采用败者树方法，每次需要，每次需要 log2w次比较。次比较。 总的时间复杂度为总的时间复杂度为O(n log2w)。 本讲完本讲完