[第八章外部排序.ppt

* * 第八章 外部分类 8.1 磁盘文件的归并分类 8.2 磁带文件的归并分类 8.1.1 K路归并 8.1.2 并行操作的缓冲处理 8.1.3 初始归并段的生成 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 假设有一个磁盘文件,其中有4500个记录,依次为A1,A2,…,A4500; 设系统可提供一个能容纳750个记录的内存工作空间供外部分类使用。 8.1 磁盘文件的归并分类 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 每次从文件中输入三个数据块共750个记录，用内部分类法进行分类，将结果写回磁盘文件中，形成6个有序的初始归并段。 R1 1-750 R2 751-1500 … R6 3751-4500 归并R1与R2,R3与R4,R5与R6 8.1 磁盘文件的归并分类 一、初始归并段的生成 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 将内存工作空间三等分。每等分能容纳250个记录，其中两块作为输入缓冲区，另一块作为输出缓冲区。 以R1与R2的归并为例: 从R1与R2中各读入250个记录； 归并好的记录写入输出缓冲区； 如果输出缓冲区满,则写入磁盘； 如果输入缓冲区空则继续读入； 直到在磁盘上形成一个长为1500的有序段。 8.1 磁盘文件的归并分类 ** 二、磁盘文件的归并过程 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 8.1.1 K路归并 一次归并K个有序段 一趟归并后长度增加多少? K倍 假如第i趟归并成,m=ki. i=logkm 8.1 磁盘文件的归并分类 假如第i趟归并完成,初始归并段个数为m Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 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的增加 比较趟数减少。 比较次数增大。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 选择树(败者树):每个结点的关键字都取它的两个子结点的关键字中较小者. 第八章 外部分类 15 16 20 38 20 30 15 25 15 50 11 16 100 110 18 20 10 9 20 6 8 9 90 17 9 6 8 17 6 8 6 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 时间复杂性分析: 第一次建树的时间复杂性为O(k-1) 以后每次的时间复杂性为O(log2k) 处理n个数据的时间为 (n-1)*log2k+O(k) 第八章 外部分类 k路归并共需logkm趟归并 O(n*log2k*logkm) = O(n*log2m) 与K路归并的K值无关。 ** Evaluation only. Created