java Nway合并对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的可用内存

1. 将文件分成K个块，其中X*K=2 GB。将每个块放入内存，并像往常一样使用任何O（n logn）算法对行进行排序。将行保存回文件

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

3. 完成后，将它们逐一合并

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

疑问：

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

Answer 1

首先，步骤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个组（每个组100万个），这意味着一个适当的N向合并将需要100K乘以20，或者大约2M，远远低于内存可用性

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

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

例如，你可以找到一个中间地带，在那里，每个通行证合并十个列表。10组100K仅为一个meg，因此将适合您的内存限制，从而减少合并过程

Answer 2

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

Answer 3

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

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