步骤,过程等相关内容讲解
树图思维导图提供 外部排序思维脑图 在线思维导图免费制作,点击“编辑”按钮,可对 外部排序思维脑图 进行在线思维导图编辑,本思维导图属于思维导图模板主题,文件编号是:c67f727d5384557bdb75a735553ae307
外部排序思维导图模板大纲
内存放不下,磁盘与内存以块为单位交换、排序、归并
作用:优化内部归并次数
例子
败者树,一图胜千言,注意,叶子其实是虚拟的
优化之处
k路归并,第一次构造败者树需要对比关键字k-1次
有了败者树,选出最小元素,至多需要对比关键字⌈logk⌉次(即层数)
作用:生成长度(可能)不等的归并段,减少初始归并段r的数量
过程及注意点
必须是选内存工作区WA中比MINNMAX大的记录中的最小值,放到归并段中
一旦选不出来,就可以新开一个归并段了
实际上,上述过程中在WA中选出MINIMAX记录的过程利用败者树实现
作用:置换-选择排序得到的归并段大小不同,利用最佳归并树来组织这些归并段使I/O最少
理论
每个初始归并段对应一个叶子结点,归并段块数 = 叶子权值
归并过程中磁盘I/O次数 =归并树WPL * 2,利用了哈夫曼树
k叉归并的最佳归并树一定是严格k叉树,树中只有度为k、0的结点
构造
构造方法和哈夫曼树一毛一样,但是要先补充虚段
利用原理:树的边数 = 顶点数 - 1
(初始归并段数量 - 1)% (k - 1) = u
补充(k - 1) - u个权值为0的虚段
如果能整除就不要补充
例如
妈的终于要结束了?
生成r个初始归并段,如果有N个记录,内存工作区只能容纳L个记录,传统方法是对L个记录内部排序,共生成r = ⌈N/L⌉个初始归并段
如图利用两个缓冲区生成初始归并段
进行S趟k路归并
S = ⌈log r⌉ (以k为底)
k个归并段的块读入k个输入缓冲区,若要并行处理:2k个输入,2个输出;k个缓冲区就要k路归并
如图,两个归并段分别放一块进去,归并后放到外存中新的位置
输出缓冲区满,写出外存;一旦输入缓冲区空,先放一块进来!
如图,这玩意知道就好,我看不能考
时间开销 = 读写外存时间 + 内部排序时间 (生成初始归并段)+ 内部归并时间
读写磁盘次数 = 文件总块数 * 2(生成初始归并段) + 文件总块数 * 2 * 归并趟数
如果有r个段,每段有n个记录,利用传统的简单选择排序选出最小值,要比较(r - 1) * (nr - 1)次,因为r个段中选出1个最小值要r-1次,而一共有nr个段,只需要选nr-1次就能选出各值的排序
王道上的习题是这样,实际当然是错的了,当选了非常多,只剩最后r个记录时,选出最小值要r-1次,剩r-1个记录,此时要r-2次了,以此类推
优化主要减少归并趟数
增加归并路数k,进行多路平衡归并
多路平衡归并
代价:增加输入缓冲区、k个归并段要k-1次对比(k路归并要k-1次对比)
减少初始归并段数量r
r越长,数量越少,归并趟数越少
树图思维导图提供 1107文家市玉萍思维导图 在线思维导图免费制作,点击“编辑”按钮,可对 1107文家市玉萍思维导图 进行在线思维导图编辑,本思维导图属于思维导图模板主题,文件编号是:ed943ef641f6dc874860eb6095857ed6
树图思维导图提供 种子思维脑图 在线思维导图免费制作,点击“编辑”按钮,可对 种子思维脑图 进行在线思维导图编辑,本思维导图属于思维导图模板主题,文件编号是:86f8307a40ea24607c6c79354e09377f