使用每行一个字符串对 20GB 文件进行排序

Question

在盖尔·拉克曼 (Gayle Laakman) 的书《破解技术面试》的问题 11.5 中，

“假设您有一个 20GB 的文件，每行一个字符串。解释一下如何对文件进行排序”

我最初的 react 正是她提出的解决方案 - 通过读取 X mb 的数据、对其进行排序，然后将其写入磁盘，将文件分割成更小的 block (兆字节)。最后，合并文件。

我决定不采用这种方法，因为最终的合并将涉及保留主内存中的所有数据 - 我们假设这是不可能的。如果是这样的话，这个解到底如何成立呢？

我的另一种方法是基于这样的假设:我们拥有接近无限的磁盘空间，或者至少足以容纳我们已有数据的 2 倍。我们可以读取 X mb 的数据，然后为它们生成哈希键 - 每个键对应于文件中的一行。我们将继续这样做，直到所有值都被散列。然后我们只需将该文件的值写入原始文件即可。

让我知道你的想法。

Answer 1

http://en.wikipedia.org/wiki/External_sorting更详细地解释了外部排序的工作原理。它通过解释如何通过读取已排序 block 的 block (而不是同时读取所有已排序 block )来执行 N 个已排序 block 的最终合并，解决了您最终必须将整个 20gB 放入内存的担忧。