19.蛤蟆的数据结构进阶十九外部排序相关概念

19.蛤蟆的数据结构进阶十九外部排序相关概念本篇名言：“一个人最怕不老实，青年人最可贵的是老实作风。老实就是不自欺欺人，做到不欺骗人家容易，不欺骗自己最难。老实作风就是脚踏实地，不占便宜。世界上没有便宜的事，谁想占便宜水就会吃亏。--徐特立”之前我们学习的排序都是内部排序的，接下去来看下外部排序。1.外部排序指的是大文件（外存文件）中的记录进行排序的过程，即待排序的记录存储在外存储器上，在排序过程中需进行多次的内、外存之间的交换。外部排序基本上由两个相对独立的阶段组成。(1)首先，按可用内存大小，将外存上含n个记录的文件分成若干长度为L的子文件或段，依次读入内存并利用有效的内部排序方法对它们进行排序，并将排序后得到的有序子文件重新写入外存。通常称这些有序子文件为归并段或顺串。(2)然后，对这些归并段进行逐趟归并，使归并段(有序的子文件)逐渐由小至大，直至得到整个有序文件为止。1.1举例说明假设有一个含10000个记录的文件，首先通过10次内部排序得到10个初始归并段R1～R10，其中每一段都含1000个记录。然后对它们作如下图所示的两两归并，直至得到一个有序文件为止。上图可见，由10个初始归并段到一个有序文件，共进行了四趟归并，每一趟从m个归并段得到[m/2]个归并段。这种归并方法称为2-路平衡归并。假设，在上例中每个物理块可以容纳200个记录，则每一趟归并需进行50次“读”和50次“写”，四趟归并加上内部排序时所需进行的读／写使得在外排中总共需进行500次的读／写。一般情况下，外部排序所需总的时间=内部排序（产生初始归并段）所需的时间M*tIS+外存信息读写的时间d*tIO+内部归并所需的时间S*utmg其中：M经过内部排序之后得到的初始归并段的个数；tIS为得到一个初始归并段进行内部排序所需时间的均值d总的读／写次数;tIO进行一次外存读／写时间的均值；S归并的趟数;utmg对u个记录进行内部归并所需时间。由此，上例10000个记录利用2一路归并进行外排所需总的时间为：10*tIS＋500*tIO＋4*10000tmg其中tIO取决于所用的外存设备，显然，tIO(进行一次外存读／写时间的均值)较tmg(内部归并所需时间)要大得多。因此，提高外排的效率应主要着眼于减少外存信息读写的次数d。1.2分析外存信息读写的次数d和“归并过程”的关系若对上例中所得的10个初始归并段进行5-路平衡归并（即每一趟将5个或5个以下的有序子文件归并成一个有序子文件），则从下图可见，仅需进行2趟归并，外排时总的读／写次数便减至2x100＋100＝300，比2-路归并减少了200次的读／写。可见，对同一文件而言，进行外排时所需读/写外存的次数和归并的趟数S成正比而在一般情况下，对m个初始归并段进行k-路平衡归并时，归并的趟数s＝[㏒km]可见，若增加k或减少m便能减少s。