第八篇外部排序.pptVIP

* * 第八章 外部分类 8.1 磁盘文件的归并分类 8.2 磁带文件的归并分类 8.1.1 K路归并 8.1.2 并行操作的缓冲处理 8.1.3 初始归并段的生成 假设有一个磁盘文件,其中有4500个记录,依次为A1,A2,…,A4500; 设系统可提供一个能容纳750个记录的内存工作空间供外部分类使用。 8.1 磁盘文件的归并分类 每次从文件中输入三个数据块共750个记录，用内部分类法进行分类，将结果写回磁盘文件中，形成6个有序的初始归并段。 R1 1-750 R2 751-1500 … R6 3751-4500 归并R1与R2,R3与R4,R5与R6 8.1 磁盘文件的归并分类 一、初始归并段的生成 将内存工作空间三等分。每等分能容纳250个记录，其中两块作为输入缓冲区，另一块作为输出缓冲区。 以R1与R2的归并为例: 从R1与R2中各读入250个记录； 归并好的记录写入输出缓冲区； 如果输出缓冲区满,则写入磁盘； 如果输入缓冲区空则继续读入； 直到在磁盘上形成一个长为1500的有序段。 8.1 磁盘文件的归并分类 ** 二、磁盘文件的归并过程 8.1.1 K路归并 一次归并K个有序段 一趟归并后长度增加多少? K倍 假如第i趟归并成,m=ki. i=logkm 8.1 磁盘文件的归并分类 假如第i趟归并完成,初始归并段个数为m 8.1.1 K路归并的比较次数 第八章 外部分类 从K个元素中选择最小值需k-1次比较. 若记录总个数为n,则需比较n(k-1) K路归并的总比较次数 n(k-1)logkm K路归并的总比较次数 n(k-1)log2m/log2k K路归并的总比较次数是(k-1)/log2k的倍数 随K的增加 比较趟数减少。 比较次数增大。 选择树(败者树):每个结点的关键字都取它的两个子结点的关键字中较小者. 第八章 外部分类 16 15 38 20 30 20 25 15 50 15 16 11 110 100 20 18 10 9 20 6 8 9 90 17 9 6 8 17 6 8 6 时间复杂性分析: 第一次建树的时间复杂性为O(k-1) 以后每次的时间复杂性为O(log2k) 处理n个数据的时间为 (n-1)*log2k+O(k) 第八章 外部分类 k路归并共需logkm趟归并 O(n*log2k*logkm) = O(n*log2m) 与K路归并的K值无关。 ** 8.1.2 并行操作的缓冲处理 在k路归并中需要k个输入缓冲区,一个输出缓冲区; 当输出缓冲区满时，这时需要把输出缓冲区的内容转移到磁盘上，归并运行要等到输出完才能开始; 同理：在输入缓冲区中，如果有一个排空，需要读入数据后才能继续进行。 8.1.2 并行操作的缓冲处理 增加一个输出缓冲区，当一个输出缓冲区满时，通知通道进行输出，同时归并程序向第二个输出缓冲区中写数据。 同理：增加k个输入缓冲区，当一个输入缓冲正在运行时，另外一个可以读数据。 8.1.2 并行操作的缓冲处理 设4个输入缓冲区为in[i],两个输出缓冲区为ou[1]和ou[2] 设有两组记录 run1:1,3,5,7,8,9 run2:2,4,6,15,20,25 8.1.2 并行操作的缓冲处理 - - O(1) O(2) - - 1 3 i(1) i(2) 2 4 - - i(3) i(4) - - 归并到O(1) 输入到i(3) 1 2 O(1) O(2) - - - 3 i(1) i(2) - 4 5 7 i(3) i(4) - - run1:1,3,5,7,8,9 run2:2,4,6,15,20,25 8.1.2 并行操作的缓冲处理 归并到O(2) 输入到i(4) - - O(1) O(2) 3 4 - - i(1) i(2) - - 5 7 i(3) i(4) 6 15 1 2 O(1) O(2) - - - 3 i(1) i(2) - 4 5 7 i(3) i(4) - - 输出O(1) run1:1,3,5,7,8,9 run2:2,4,6,15,20,25 8.1.2 并行操作的缓冲处理 归并到O(1) 输入到i(1) 5 6 O(1) O(2) - - 8 9 i(1) i(2) - - - 7 i(3) i(4) - 15 输出O(2) - - O(1)