N-way merge对2G字符串文件进行排序

Question

这是我接受采访时提出的另一个问题，看完后我仍然有些怀疑。

9.4 If you have a 2 GB file with one string per line, which sorting algorithm 
    would you use to sort the file and why?

解决方案

当面试官给出2GB的大小限制时，它应该告诉你一些事情——在这种情况下，它表明他们不希望你将所有数据带入内存。那么我们该怎么办？我们只将部分数据带入内存...算法：

我们有多少可用内存？假设我们有X MB的可用内存。

>

现在将下一个块放入内存并进行排序。

一旦我们完成了，一个接一个地合并它们。

上述算法也称为外部排序。第3步被称为N-way merge使用外部排序的基本原理是数据的大小。由于数据太大，我们无法将其全部存储在内存中，因此我们需要采用基于磁盘的排序算法。

疑问：

在第3步中进行合并排序时，在比较两个数组时，每次比较是否需要2*X的空间？限制是X MB。我们应该把这些块做成（X/2）*2K=2GB吗？因此，每个区块将是X/2MB，将有2K个区块。或者我只是理解错了合并排序？谢谢

Answer 1

合并过程要简单得多。您将把它们输出到一个新文件，但基本上只需要恒定的内存：一次只需要从两个输入文件中读取一个元素。

Answer 2

首先，步骤3本身不是一个合并排序，整个过程是一个合并排序。第3步只是合并，根本不涉及排序。

至于所需的存储空间，有两种可能性。

第一种方法是将排序后的数据合并为两组。假设你有三个小组：

A: 1 3 5 7 9
B: 0 2 4 6 8
C: 2 3 5 7

使用该方法，您可以将A和B合并到一个组Y中，然后将Y和C合并到最终结果Z中：

Y: 0 1 2 3 4 5 6 7 8 9         (from merging A and B).
Z: 0 1 2 2 3 3 4 5 5 6 7 7 8 9 (from merging Y and C).

这有一个非常小的恒定内存需求的优点，即您只需要存储两个列表中的“下一个”元素，但当然，您需要执行多个合并操作。

第二种方法是“正确的”N路合并，您可以从任何组中选择下一个元素。这样，您就可以检查每个列表中的最低值，看看下一个是哪个：

Z: 0 1 2 2 3 3 4 5 5 6 7 7 8 9 (from merging A, B and C).

这只涉及一个合并操作，但需要更多存储，基本上每个列表一个元素。

您选择哪一个取决于可用内存和元素大小。

例如，如果您有100M可用存储器，并且元素大小100K，您可以使用后者。这是因为，对于2G文件，您需要20组（每组100M）用于排序阶段，这意味着正确的N路合并需要100K20或大约2M，远低于您的内存可用性。

或者，假设你只有100万美元可用。这将是大约2000（2G/1M）组，再乘以10万就有2亿组，远远超出你的容量。

所以你必须在多个过程中进行合并。但是请记住，它不一定是合并两个列表的多个过程。

例如，你可以找到一个中景，每个通道合并十个列表。十组100K只是一个meg，所以将适合你的内存限制，这将导致更少的合并通道。

Answer 3

http://en.wikipedia.org/wiki/External_sorting

快速浏览Wikipedia告诉我，在合并过程中，您永远不会在内存中保存整个块。因此，基本上，如果您有K个块，您将有K个打开的文件指针，但在任何给定时间，您只会在内存中的每个文件中保存一行。您将比较内存中的行，然后将最小的行（例如，从第5块）输出到您的排序文件（也是一个打开的文件指针，不在内存中），然后用该文件（在我们的示例中，文件5）的下一行覆盖该行到内存中并重复直到您到达所有块的末尾。