9

这是破解编码面试中的另一个问题，我看完后仍然有些疑问。

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 log n) 算法对行进行排序。将这些行保存回文件。

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

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

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

怀疑：

在第 3 步进行归并排序时，在比较 2 个数组时，每次比较是否需要 2*X 空间？限制是 X MB。我们应该把块做成 (X/2)*2K = 2GB 吗？这样每个块将是 X/2 MB 并且将有 2K 块。或者我只是理解合并排序错误？谢谢！

4

3 回答 3

9

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

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

于 2012-05-21T00:52:26.893 回答
6

首先，第 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 路合并将需要 100K x 20，或大约 2M，这远远低于您的内存可用性。

或者，假设您只有 1M 可用。这将是大约 2000 (2G / 1M) 组，将其乘以 100K 得到 200M，远远超出您的容量。

所以你必须在多遍中进行合并。请记住，它不一定是合并两个列表的多次传递。

您可以找到一个中间地带，例如，每个通道合并十个列表。十组 100K 只是一个兆，因此将适合您的内存限制，这将导致更少的合并通过。

于 2012-05-21T00:50:54.600 回答
2

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

于 2012-05-21T00:49:31.483 回答