学步园

外部排序

Eg - 数据结构与算法分析 外部排序
noteton

必要性

　　大部分内部排序算法都用到内存可直接寻址的事实。如果输入数据再磁盘上，那么所有这些操作都失去了它们的效率，因为磁带上的元素只能被顺序访问。
　　外排序通常采用的是一种“排序-归并”的策略。在排序阶段，先读入能放在内存中的数据量，将其排序输出到一个临时文件，依次进行，将待排序数据组织为多个有序的临时文件。而后在归并阶段将这些个临时文件组合成一个大的有序文件，也即排序结果。

外规定排序

　　外部排序的一个例子是外归并排序（External Merge Sort），它先读入一些能够在内存中放得下的数据量，在内存中排序后输出为一个顺串（即内部数据有序的临时文件），处理完所有的数据后在进行归并。
　　比如：要对900MB的数据进行排序，但机器上只有100MB的可用内存时，外归并排序按如下方法操作：
　　1. 读入100MB的数据至内存中，用某种常规排序（如：快速排序、堆排序、归并排序等）在内存中完成排序。
　　2. 将排序完成的数据写入磁盘（临时文件）。
　　3. 重复步骤1和步骤2直到所有的数据都存入了不同的100MB的块（临时文件）中。本例中，900MB数据，100MB内存，故产生了9个临时文件。
　　4. 读入每个临时文件（顺串）的前10MB(=100MB/(9块+1)，在进行多路归并的时候，这里有9路，然后输出缓冲算一个，所以要将内存资源分给10个部分)的数据放入内存中的输入缓冲区（总计90MB），最后的10MB作为输出缓冲区。（实践中，将输入缓冲适当调小，而适当增大输出缓冲区能获得比较好的效果）
　　5. 执行九路归并算法，将结果输出到输出缓冲区。一旦输出缓冲区满，将缓冲区中的数据写到目标文件，清空缓冲区。一旦9个输入缓冲区的一个变空，就从这个缓冲区关联的文件中读入下一个10MB数据，除非这个文件已读完。这是“外归并排序”能在主存外完成排序的关键步骤——因为“归并算法（merge algorithm）”对每一个大块只是顺序地做一轮访问（进行归并），每个大块不用完全载入主存。
　　1-3步是排序，4-5步是归并。
　　为了增加每一个有序的临时文件的长度，可以采用置换选择排序（Replacement Selection Sorting）。它可以产生大于内存的顺串。具体方法是在内存中使用一个最小堆进行排序，设这个最小堆的大小为M，算法描述如下：
　　1. 初始时将输入文件读入内存，建立最小堆。
　　2. 将堆顶元素输出至输出缓冲区。然后读入下一个记录。
　　 2.1 若该元素的关键码值不小于刚输出的关键码值，将其作为堆顶元素并调整堆，使之满足对的性质。
　　 2.2 若该元素的关键码值大于刚输出的关键码值，将新元素放入堆底位置，将堆的大小减1。
　　3. 重复第2步，直至堆大小变为0。
　　4. 此时一个顺串已经产生。将堆中的所有元素建堆，开始生成下一个顺串。
　　此方法能生成平均长度为2M的顺串（证明？？？），可以进一步减少访问外部存储器的次数，节约时间，提高算法效率。

附加的步骤

　　上述例子的外排序主要有两个步骤：排序和归并；我们用一次多路归并就完成了所以临时文件的归并，并非按照内排序那样利用内存而采用二路归并，一次归并两个字串，耗费log2n次归并。外排序中不适合这种二路排序的原因是每次读写都要对硬盘进行读写，非常缓慢，要极力减少对磁盘的读写次数。
　　不过，在上述方法中也存在权衡的问题。当临时文件（顺串）的数量继续增大时，归并时每次从顺串中读入的数据减少了。比如说，50GB的数据量，100MB的可用内存，这种情况下用一趟多路归并就显得不划算。因为读入很多的顺串花费的时间占据了排序时间的大部分。这时，我们可以考虑用多次（比如两次）归并来解决问题。（注意多次归并和多路归并的区别）
　　这时排序算法变为下述这样：
　　1. 第一步不变：初始时将输入文件读入内存，建立最小堆。
　　2. 将小的顺串合并为大一些的顺串，适当减少顺串的数目。
　　3. 将剩余的大一些的顺串归并为最终结果。
　　即先归并小的顺串成较大的顺串，然后再归并大一些的顺串至最终结果。和内排序一样，高效的外排序所耗的时间依然是O(nlogn)。若利用好现在计算机上GB的内存，可使得时间复杂度汇总的对数项增长比较缓慢。

优化性能

　　计算机科学家吉姆·格雷的Sort Benchmark网站用不同的硬件、软件环境测试了实现方法不同的多种外排序算法的效率。效率较高的算法具有以下的特征：
　　1. 并行计算
　　 · 用多个磁盘驱动器并行处理数据，可以加速顺序磁盘读写。
　　 ·在计算机上使用多线程，可在多核心的计算机上得到优化。
　　 ·使用异步输入输出，可以同时排序和归并，同时读写。
　　 ·使用多计算机用高速网络连接，分担计算任务。
　　2. 提高硬件速度
　　 ·增大内存，减小磁盘读写次数，减少归并次数。
　　 ·使用快速的外存设备，比如15000RPM的硬盘或固态硬盘。
　　 ·使用性能更加优良的各种设备，比如使用多核心CPU和延迟时间更短的内存。
　　3. 提高软件速度
　　 ·对于某些特殊数据，在第一阶段的排序中使用基数排序。
　　 ·压缩输入输出和临时文件。

其他算法

　　外归并排序法并不是唯一的外排序算法，另外还有外分配排序，其原理类似于内排序中的桶排序。在归并排序和桶排序之间存在数学上的对偶性。此外还有一些不耗费附加磁盘空间的原地排序算法。

参考资料

　　主要参照wiki的外排序;

资源链接

• STXXL: Standard Template Library for Extra Large Data Sets.
• [外归并排序实例](http://cis.stvincent.edu/html/tutorials/swd/extsort/extsort.html)
• Java语言外归并排序

　　看到v_JULY_v大牛的博客，对这类问题有一个更详细的总结，于是，决心另拟一篇博文作为拜读大牛作品的笔记。