学科分类
目录
数据结构

磁盘排序分析

因为内存空间有限,所以每次进入内存中参与排序的只是完整文件的一部分。对于磁盘排序:在排序开始之后,首先需要根据内存空间的大小,将完整文件划分成若干个长度为l的子文件(子文件又称为段);然后将这些子文件依次读入内存中,使用内部排序方法为每一个子文件排序后,再重新写回外存,此时已各自有序的子文件称为归并段或者顺串;之后对这些归并段进行归并,直到所有归并段组成有序的完整文件为止。如图1所示为一次完整的磁盘排序过程。

图1 磁盘排序过程示意

由图1可以看出,文件F首先从外存被读入内存,在内存中经内存排序处理之后,生成归并段重新写回外存,此时的每个归并段都是有序的,且归并段之间的相对次序也是确定的;之后使用某种归并方法对归并段进行归并排序,这一过程仍要借助内存来完成,其间同样有读/写操作发生。

假设现有一待排序文件F,F中包含6000条记录。若内存WA依次最多能对600条记录进行排序,内存每次读/写包含200条记录的物理块。那么内存每次读入3个物理块,并对读入的物理块进行内排序,生成一个初始归并段。因此文件F被分为10个归并段,每个归并段中包含600条记录,记为F1~F10。若使用2-路归并排序对这10个归并段进行归并,由图2可知,经过4次归并,这10个归并段被归并为一个有序文件。

图2 归并段的2-路归并过程

在生成归并段之前,F中的6000条记录先分块被扫描一遍,经过读操作进入内存。已知每个物理块包含200条记录,那么扫描完毕时文件F被读/写各30次,其间每读入一个物理块,这些数据便在内存中被排序,排序完毕的数据被重新写回外存,成为一个归并段。

之后对生成的归并段F1~F10进行归并排序。此时将内存分为3块,每块能容纳200条记录,其中两块作为输入缓冲区,用来存放读入内存的记录;另外一块作为输出缓冲区,用来存放归并过程中排好序的记录,当输出缓冲区存满时,进行一次写操作,将其中的记录写到外存。

假设生成一个初始归并段(内部排序)耗费的时间为tg,内存从外存读或者向外存写一个物理块耗费的时间为tIO,对u条记录进行内部归并耗费的时间为ut,归并的轮数为s,归并段的数量为m,信息读写次数为r,那么进行一次磁盘排序所需的时间为:

相比而言,内部排序耗费的时间远小于内外存之间的读写时间,又因为生成初始归并段的时间确定(因为物理块大小确定),所以若要提高外部排序效率,应该尽量减少读写的次数r。

那么该如何减少读写次数呢?由以上分析可知,读写操作主要发生在归并的过程中,读写次数也就与归并排序中归并的轮数有关,归并的轮数越少,读写的次数也就越少。若归并段的数量为m,假设使用k-路归并排序进行归并,那么归并的轮数image-20200629090833323,归并轮数n与初始归并段数量m成正比,与k成反比,也就是说,初始归并段的数量越少,或者归并时的k值越大,归并的轮数就越少。

分析图2中的2-路归并排序:第一次归并过程,所有记录都被扫描一遍,经过30次读操作和30次写操作,归并段的数量减少为5个;第二次归并过程中,归并段F1′~F4′各被扫描一遍,经过48次读/写操作,归并段的数量减少为3个;第三次归并过程中,归并段F1″和F2″各被扫描一遍,经过48次读/写操作,归并段的数量减少为2个;最后一次归并过程中,当前仅有的两个归并段各被扫描一遍,经过60次读/写操作,这两个归并段被归并为一个有序文件。整个过程读写次数为276次。

若使用4-路归并对这10个归并段进行归并,由图9-55可知,归并执行的轮数为2。两轮归并最多将文件F扫描三遍,那么读写次数不超过180次。

图3 归并段的4-路归并过程

若初始归并段只有2个,那么仅需一次归并排序即可完成外排序,归并中读写总次数为60,但是初始归并段的数量受到内存容量的限制,所以只能在合适的范围内调整。

点击此处
隐藏目录