第十章外部排序.ppt

第十章外部排序 外存信息的存取外部排序的基本方法 归并排序法多路平衡归并置换 选择排序 外部排序的应用对象保存在外存储器上的信息量很大的数据记录文件 外排序与内排序的差别内部排序充分利用内存可以随机存取的特点 如希尔排序中 相隔di的记录关键字可作比较 堆排序中 完全二叉树中父R i 与子R 2i R 2i 1 可比快速排序中 需正向和逆向访问记录序列外存信息的定位和存取受其物理特性的限制外部排序的实现手段在排序过程中 进行多次内外存之间的数据交换 外部排序的特点 外排序基本方法 归并排序 步骤 1 生成顺串生成若干初始归并串 顺串 文件预处理 把含有n个记录的文件 按内存缓冲区大小分成若干长度为L的子文件 段 分别调入内存用有效的内排序方法排序后送回外存 2 合并顺串多路合并对初始归并串逐趟合并 直至最后在外存上得到整个有序文件为止 例 某文件共10000个记录 设每个物理块可以容纳200个记录 内存缓冲区可以容纳5个物理块 每段含1000个记录 1 经过10次内排序后得到10个初始归并段R1 R102 采用两路归并 需四趟可以得到排好序的文件R1R2R3R4R5R6R7R8R9R102000200020002000200040004000200080002000内排序 10tIS10000I O操作 100tIO 排序 100 80 80 100 tIO 归并 460tIO归并 10000 8000 8000 10000 tmg 46000tmg 外部排序分析 外部排序所需总时间T m tIs d tI O s ntmg其中tIs是构造一个初始归并段所需内部排序的平均时间 m为初始归并段的个数 tI O是进行一次外存读 写的平均时间 d为总的读 写次数 tmg是对一个记录进行内部归并所需时间 n为记录个数 s为归并的趟数 提高外排序效率的途径 扩大初始归并段长度 从而减少初始归并段个数m进行多路 k路 归并 减少合并趟数s 以减少I O次数s logkm 11 3多路归并排序 k 路归并 n个记录分布在k个归并段上 从k个记录中选出一个最小记录需进行k 1次比较 一趟归并要得到全部n个记录共需进行 n 1 k 1 次比较 此k 路归并排序的内部归并过程中进行的总的比较次数为s n 1 k 1 故有 k s 可减少I O次数 k c k 1 归并效率 利用 败者树 选关键字最小的记录 此时从k个记录中选出一个最小记录需进行log2k次比较 则C log2m n 1 与k无关 败者树 败者树是一颗完全二叉树叶结点存放参加比较的记录非叶结点记忆其子女结点中的败者根结点之上的结点存放最后的胜者 胜者树 树形选择排序 68689896890915890109206812109201581210920681290109201581290142224151617921422242516179226383025501897263830 501897 7路合并胜者树重构后的胜者树重构胜者树时 从根结点至新补入记录的叶结点的路径上的所有结点都必须更新 实现5 路归并的败者树 败者树 5220401369013690109206812109201581210920681290109201581290142224151611921422242516119226383025501897263830 501897 7路合并败者树重构后的败者树败者树的特点 记录败者 胜者参加下一轮比赛败者树的优点 重构时修改结点较少 0 123456 4 ls 0 5 ls 0 123456 0 7777777900109206812123456 k 路归并对内存的要求 至少要有k个输入缓冲区和一个输出缓冲区 建败者树的过程 7 1 初始化败者树 调整b 6 6 调整b 5 5 调整b 4 4 调整b 3 3 4 调整b 2 2 调整b 1 1 2 4 调整b 0 0 5 4 建败者树的过程 4520136900109206812123456调整败者树的方法 将新补充的结点与其双亲结点比较 败者留在该双亲结点 胜者继续向上直至树根的双亲 以在b 4 补充15为例 15 4与3比较 4与2比较 4 2与5比较 2 5 调整败者树的方法 数据结构 败者树为完全二叉树 主 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 i 0 i Adjust i voidAdjust ints for t s k 2 t 0 t 2 if b s b ls t s ls t ls 0 s 算法描述 K路合并 voidK Merge for i 0 i k i input i 第i路输入一个元素到b i CreateLoserTree ls while b ls 0 MAXKEY q ls 0 output b q input q Adjust q 11 4置换 选择排序 目标 扩大初始归并段长度 突破内存工作区容量 设w个记录 的限制 置换 选择排序原理 内存外存原始文件内存工作区FIWA初始归并段文件 w个记录 FO为简化问题 设每个物理块存放一个记录 1 从FI输入w个记录到工作区WA 在FO中标记一个归并段开始 2 从WA中选出最小关键字记录 记为minimax记录 3 将minimax记录输出到FO中 4 从FI输入下一个记录到WA中 5 在WA中的关键字比minimax大的记录中选出关键字最小的记录 作为新的minimax记录6 重复3 5 直至在WA中选不出为止 在FO中标记一个归并段结束 7 重复2 6 直至WA为空 则结束处理 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的两倍 11 5最佳归并树 文件经过置换 选择排序之后 得到长度不等的初始归并段 进行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 446 3 路归并 所有叶结点加权外通路长度的2倍 IO 方案二 方案一 最佳归并树的构造 最佳归并树即k叉 阶 哈夫曼树 设初始归并段为m个 进行k 路归并1 若 m