高效的核外排序

Question

我正在尝试研究如何有效地排序不适合内存的巨大数据集.高级别的明显答案是使用一些标准算法对一大堆适合内存的块进行排序,将这些块写入磁盘,然后合并它们.合并它们是问题所在.

假设数据分为C块,所以我要合并C文件.如果我在一次传递中进行C-way合并,那么从技术上讲,我有一个O(N ^ 2)算法,尽管只需要执行O(N)写入磁盘.如果我迭代地将它们合并到C/2文件,然后是C/4文件等,那么我有一个O(N log N)算法,但是一个必须执行O(N log N)写入磁盘,因此一个巨大的常数.

这个难题的典型解决方案是什么？有什么好的吗？

Answer 1

简单的答案是这个问题没有简单的答案.有很多答案,其中大部分都相当复杂 - Knuth第3卷(仅举一例)为它投入了大量的空间.

在查看已完成的操作时,有一点很明显,您确实希望最小化在初始排序期间创建的文件数量,并最大化每个文件的长度.要做到这一点,你通常希望尽可能多地读入内存中的数据,但是不要只是将其排序并写出来,而是要将它放入堆中.然后当你写出每条记录时,你会读取另一条记录并将其放入堆中.当您将每个后续记录从堆写入文件时,检查它是否大于现有记录.如果没有,则将其从堆中删除,然后将其插入另一个堆中.然后继续第一个堆中的下一个最小记录.当第一个堆完全为空时,您停止将记录放入当前文件,并且您的第二个堆占用了所有内存.此时,您开始将记录放入新文件中,并基本上"交换"两个堆的使用.

这将在初始阶段产生相当长的中间文件,因此合并它们的工作量大大减少.

编辑:我当然没有发明这一点 - 我可能首先在Knuth中阅读它,但也许在算法+数据结构=程序(Niklaus Wirth) - 都讨论它.Knuth在1954年的麻省理工学院硕士论文中首次将该方法发表于"H. Seward".如果你有第二版的Knuth,那就是第3卷第254页.我从来没有得到过副本第三版,所以我没有页码.

Answer 2

一个好的解决方案是外部排序.具体检查外部mergesort算法.

外部排序是一类可以处理大量数据的排序算法的术语.当被排序的数据不适合计算设备(通常是RAM)的主存储器时,需要进行外部排序,而是必须将它们驻留在较慢的外部存储器(通常是硬盘驱动器)中.典型的外部排序算法使用排序合并策略,该策略从排序小子文件开始.基本算法包括两个阶段:排序阶段和合并阶段.在排序阶段,子文件可以放入可用缓冲区空间,读入主内存,使用内部排序算法排序,并作为临时排序子文件写回磁盘.在合并阶段,排序的子文件在一次或多次传递期间合并.

Answer 3

有趣的是，一个月前我听到了同样的问题……以及我们当地的专家也给予了答复。

“使用unix排序命令”

尽管我们承认这是在以骗子为代价而开玩笑，但事实并非如此。原因是那些聪明的人已经对如何解决超大文件的问题进行了很多思考，并提出了一个非常令人印象深刻的实现，它充分利用了可用资源。

因此，除非您打算重新发明轮子：即您有时间，而这对业务至关重要，那么简单地使用unix sort可能是一个好主意。

唯一的缺点是其奥秘的语法。此页面专用于命令和各种说明。

我的个人建议：抽取一小部分数据样本，以测试该命令有效地执行了您想要的操作。