《数据结构外部分类》PPT课件.ppt

7.1磁盘文件的归并分类7.2磁带文件的归并分类,第7章外部分类（Sorting）,归并方法：首先将文件中的数据输入到内存，采用内部分类方法进行分类（归并段），然后将有序段写回外存；对多归并段进行多遍归并，最后形成一个有序序列。,例：假设一个磁盘文件，由4500个记录组成，分别记为A1,A2,A4500设系统提供容纳750个记录的内存共分类使用，每次磁盘读写250个记录的数据块，则可设计分类过程如下：,7.1磁盘文件的归并分类,(1)每次从文件中输入三个数据块（750个记录）到工作空间，进行内部分类。分类结果写回磁盘，构成6个初始归并段：R1,R2,R3,R4,R5,R6,（2）将内存空间三等分，每块250个记录，其中2块为输入缓冲区，1块为输出缓冲区。归并R1和R2，输出到输出缓冲区，若输出缓冲区满，则写盘。同样，若R1和R2的缓冲区出现空，则继续读盘，直到归并结束为止。R12=R1+R2；同样得到：R34=R3+R4,R56=R5+R6；R12、R34、R56分别都包含1500个记录。,（3）类似（2）的方法，可将R12和R34归并成R1234,，再将R1234和R56进行归并。得到最后的排序结果。,logkm遍比较次数：,(1)多路归并减少归并遍数,m个初始段进行2路归并，需要log2m遍归并;一般地，m个初始段，采用k路归并，需要logkm遍归并。,显然，k越大，归并遍数越少，可提高归并的效率。,在k路归并时，从k个关键字中选择最小记录时，要比较K-1次。若记录总数为n，每遍要比较的次数为：n*(k-1)log2m/log2k可以看出，随着k增大，(k-1)/log2k也增大，当归并路数多时，CPU处理的时间也随之增多。为此要选择好的分类方法，以减少分类中比较次数。,选择树(Selectiontree)或败者树(treeofloser),分析：,第一次建立选择树的比较所花时间为:O(k-1)=O(k)而后每次重新建造选择树所需时间为：O(log2k)n个记录处理时间为初始建立选择树的时间加上n-1次重新选择树的时间：O(n-1)log2k)+O(k)=O(nlog2k)这就是k路归并一遍所需的CPU处理时间。归并遍数为logkm，总时间为：O(nlog2klogkm)=O(nlog2m)(k路归并CPU时间与k无关),最佳归并树,将哈夫曼树进行拓展，不仅对二叉树，同样可形成三叉、四叉、k叉树，亦称为哈夫曼树，同样可求得带权路径长度最小。,最佳归并树：对长度不等的m个初始归并段，构造哈夫曼树作为归并树，便可使在进行外部归并时所需要对外存进行的读写次数达到最小。,最佳归并树中，并不只是只有度为k和0的结点，会有缺额。当初始归并段的数目不足时，需附加长度为0的虚段，按照哈夫曼树的构造原则，权为0的叶子结点应离树根最远。,若(m-1)%(k-1)=0则不需要附加虚段；否则需要附加：k-(m-1)%(k-1)-1个虚段。,第一次归并的路数为：(m-1)%(k-1)+1,并行操作的缓冲区处理使输入、输出和CPU处理尽可能重叠,对k个归并段进行k路归并至少需要k个输入和1个输出缓冲区，要使输入、输出和归并同时进行，k+1个缓冲区是不够的，需要2k个输入缓冲区实现并行操作。,135789,246152025,(3)初始归并段的生成,(a)初始归并段的长度缓冲区的长度,(b)任何内部分类算法都可作为生成初始归并段的算法,(c)例如：缓冲区的长度为4，输入序列为：151904831227112516342607109006,新输入记录.key小于当前记录.key，等待下一个归并段,采用选择树法生成初始归并段的长度平均是缓冲区长度的两倍。,7.2磁带文件的归并分类,（外部）存储设备纸带、磁鼓、磁带、磁盘等,与磁盘不同，磁带是顺序存储设备，读取信息块的时间与信息块的位置有关。研究磁带分类，需要了解信息块的分布。,K路平衡归并分类,磁带机数量：2k,注：在多路归并中，若要求归并的文件其初始归并段总数不是K阶Fibonacci数，则需附加一些虚的归并段数，以凑成k阶Fibonacci数，同时还应该将虚归并段适当地分布在k路归并的k台磁带上。,例1：设有磁盘文件中记录的关键字分别为：10,20,15,25,12,13,21,30,8,16,10用置换-选择排序法产生初始归并段，问可产生几个初始归并段？每个初始归并段包含哪些记录（设工作区能容纳4个记录）。,解：内存缓冲区可容纳4个记录，采用4路归并的置换-选择排序方法生成初始归并段，如表所示。,例2：给出一组关键字T=(12,2,16,30,8,28,4,10,20,6,18),设内存工作区可容纳4个记录，写出用置换-选择排序得到的全部初始归并段。,解：初始归并段1：2,8,12,16,28,30初始归并段2：4,6,10,18,20,例3：设有13个初始归并段，其长度分别为：28,16,37,42,5,9,13,14,20,17,30,12,18。试画出4路归并时的最佳排序树，并计算它的带权路径长度。,解：n=13,k=4因为(n-1)%(k-1)=0,所以不需要加虚段。,WPS=(5+9+12+13+14+16+17+18+20+28+30+37)2+42=480,例：假设4个初始归并段如下：R1:15,16,25,32R2:3,22,28,45R3:1,12,30,42R4:33,60给出进行4路归并的过程。,(1)输出1R1:15,16,25,32R2:3,22,28,45R3:12,30,42R4:33,60,(2)输出1,3R1:15,16,25,32R2:22,28,45R3:12,30,42R4:33,60,(3)输出1,3,12R1:15,16,25,32R2:22,28,45R3:30,42R4:33,60,(4)输出1,3,12,15R1:16,25,32R2:22,28,45R3:30,42R4:33,60,(5)输出1,3,12,15,16R1:25,32R2:22,28,45R3:30,42R4:33,60,(6)输出1,3,12,15,16,22R1:25,32R2:28,45R3:30,42R4:33,60,(7)输出1,3,12,15,16,22,25R1:32R2:28,45R3:30,42R4:33,60,(8)输出1,3,12,15,16,22,25,28R1:32R2:45R3:30,42R4:33,60,(9)输出1,3,12,15,16,22,25,28,30R1:32R2:45R3:42R4:33,60,(10)输出1,3,12,15,16,22,25,28,30,32R1:R2:45R3:42R4:33,60,(11)输出1,3,12,15,16,22,25,28,30,32,33R1:R2:45R3:42R4:60,(12)输出1,3,12,15,16,22,25,28,30,32,33,42R1:R2:45R3:R4:60,(13)输出1,3,12,15,16,22,25,28,30,32,33,42,45R1:R2:R3:R4:60,(14)输出1,3,12,15,16,22,25,28,30,32,33,42,45,60R1:R2:R3:R4:,归并结束,例：假设某文件经内部排序得到100个初始归并段，试问：(1)若使用多路归并3趟完成排序，则应取归并的路数至少为多少？(2)假设操作系统要求一个程序同时可用的输入、输出文件的总数不超过3个，则按多少路归并至少需要几趟可以完成排序？如果限定这个趟数，则可取的最低路数是多少？,解：(1)m=100,s=3s=logkm=2得k至少为5。,(2)因为输入输出的文件总数不超过13个，所以每次可取12个文件作为输入，1个文件作为输出，这就是说每次可取12路进行归并，则至少需2趟归并排序。如果限定归并趟数为2，对于总数为100的初始归并段，则进行10路归并即可。,