TreeMind树图在线AI思维导图
当前位置:树图思维导图模板IT互联网产品结构外部排序思维脑图思维导图

外部排序思维脑图思维导图

  收藏
  分享
免费下载
免费使用文件
生杀予夺 浏览量:92023-12-17 16:01:50
已被使用0次
查看详情外部排序思维导图

步骤,过程等相关内容讲解

树图思维导图提供 外部排序思维脑图 在线思维导图免费制作,点击“编辑”按钮,可对 外部排序思维脑图  进行在线思维导图编辑,本思维导图属于思维导图模板主题,文件编号是: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个归并段的块读入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文家市玉萍思维导图 在线思维导图免费制作,点击“编辑”按钮,可对 1107文家市玉萍思维导图  进行在线思维导图编辑,本思维导图属于思维导图模板主题,文件编号是:ed943ef641f6dc874860eb6095857ed6

种子思维脑图思维导图

树图思维导图提供 种子思维脑图 在线思维导图免费制作,点击“编辑”按钮,可对 种子思维脑图  进行在线思维导图编辑,本思维导图属于思维导图模板主题,文件编号是:86f8307a40ea24607c6c79354e09377f