云大数据结构课程教学课件外部排序.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 第十一章 外部排序 第一节 外部信息的存取 * 外存信息的存取 计算机存储器: 内存储器(主存)和外存储器(辅存). 外存储器包括磁带和磁盘(或磁鼓).前者为顺序存取,后者为随机存取. 磁带信息的存取: 写入头 读出头 接受盘 源盘 * 磁带信息的存取 磁带是一种起停设备, 因此在磁带上相邻两组字符组（记录）之间要留一空白区：叫做间隙IRG ( Inter Record Gap) 为了利用资源，将组成块来减少IRG的个数。每个字符组间就没有了IRG，而变成块间间隙IBG(Inter Block Gop) IRG 记录 20个记录组成的块 IBG * 磁盘信息的存取 磁盘是一种直接存取的存储设备（DASA） 第二节 外部排序的方法 * 外部排序 外部排序由两个相对独立的阶段组成。 首先：按可用内存大小，将外存上含N个记录的文件分成若干长度为L的子文件或段(segment),依次读内存并进行内部排序，再将得到的子文件重新写入外存，通常称这些有序子文件为 归并段或顺串(run); 然后：对这些段进行逐趟归并，使归并段逐渐由小到大，直至得到整个有序文件。 * 外部排序示例 R1 R3 R2 R4 R5 R6 R7 R8 R1’ R4’ R3’ R2’ R9 R10 R5’ R1’’ R2’’ R3’’ R1’’’ R2’’’ 有序文件 * 2-路平衡归并 示例中，由10个初始归并段到一个有序文件，共运行了4趟归并，每一趟从m个归并段得到『m/2』个归并段。这种归并方法叫2-路平衡归并。 外部排序所需总的时间为＝ 内部排序(产生初始归并段)所需的时间 + 外存信息读取的时间 + 内部归并所需的时间 * 5-路平衡归并 R1 R3 R2 R4 R5 R6 R7 R8 R9 R10 R1’ R2’ 有序文件 * k-路平衡归并 进行外排时所需读/写外存的次数和归并的趟数s成正比。 对m个初始归并段进行k-路平衡归并时，归并的趟数 第三节 多路平衡归并的实现 * 2-路平衡归并的实现 进行U－1次比较 U个记录分布在2个归并段上 * k-路平衡归并的实现 U个记录分布在k个归并段上 进行(U－1)(k－1)次比较 * 多路平衡归并的实现 对n个记录的文件进行外排时，在内部总的比较次数为 s(k-1)(n-1) * 胜者数 27 27 38 65 38 76 27 27 胜者数(选出最小关键字) 冠军 * 败者数 38 76 38 65 65 76 27 27 败者数(选出最小关键字) 冠军 * 实现5-路归并的败者数 6 15 25 9 18 20 10 15 16 12 37 48 20 22 40 6 12 10 9 20 4 0 2 1 3 1 0 2 4 3 b3 b4 b0 b1 b2 记录败者的段号 指示出最小关键字为第3段中的当前记录 * 实现5-路归并的败者数 15 25 9 18 20 10 15 16 12 37 48 20 22 40 15 12 10 9 20 4 0 2 1 3 1 0 2 4 3 b3 b4 b0 b1 b2 和双亲结点所指的关键字进行比较 3 4 0 1 第四节 置换----选择排序 * 归并的趟数不仅和k成反比，也和m成正比。 m =[ n / l ] 其中n为外部文件的记录数，l为初始 归并段中的记录数 置换----选择排序 L个记录 n个记录 * 置换----选择排序 置换----选择排序 是数形选择的变形。特点：在整个排序(在得到所有初始归并段)的过程中，选择最小(或最大)关键字和输入、输出交叉或平行进行。 65 97 76 13 27 49 49 38 65 38 13 27 38 13 13 数形选择 * 置换----选择排序 已知文件含有24个记录。假设内存工作区可容纳6个记录。 选择排序结果 置换－－选择排序结果 51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 36 76 51 49 39 46 38 29 14 61 15 30 1 48 52 3 63 27 4 13 89 24 46 58 36 76 * 置换----选择排序 FI WA FO 51 49 39 46 38 29 14 61 15 30 1 48