c++ - 在具有 1GB RAM 的机器上对 1TB 文件进行排序

Question

这个问题看似简单，但我无法理解其背后的真正工作。我知道人们会说，分解成 512 Megs block 并像使用 Map reduce 使用合并排序一样对它们进行排序。

所以这是我的实际问题:

假设我将文件分成 512 Megs block ，然后发送到不同的主机对它们进行排序。假设这些机器使用合并排序。现在说，我有 2000 台机器，每台机器排序 2000，512 兆 block 。现在，当我将它们合并回来时，它是如何工作的？尺寸不会再继续增加吗？例如，合并两个 512 兆将产生 1024 兆，这是我的 RAM 的大小，那么这将如何工作？任何机器都不能将超过 512 兆 block 的 block 与另一个 block 合并，因为这样大小会 > 1 GB。

在合并结束时，我如何才能将两个 0.5 TB block 与另一个 0.5 TB block 合并。虚拟内存的概念在这里发挥作用吗？

我来这里是为了澄清我的基础知识，我希望我能正确地(正确地)问这个非常重要的问题。另外，谁应该做这个合并(排序后)？我的机器还是那 2000 台机器中的几台？

Answer 1

这个问题可以简化为一个更简单的问题。这个问题旨在迫使您采取一种方法。在这里:

• 选取 block =~ 1GB，排序并将它们存储为单独的排序文件。
• 最终文件系统上有 1000 个 1GB 的排序文件。

• 现在，这只是一个将 k 排序数组合并为一个新数组的问题。

  合并 k 排序数组需要您同时维护一个包含 k 个元素的最小堆(优先级队列)。

即k = 1000(文件)在我们的例子中。 ( 1GB内存可存储1000个数字 )

因此，从优先级队列中弹出元素并保存到磁盘。

您将有一个新文件，大小为 1TB。

引用:http://www.geeksforgeeks.org/merge-k-sorted-arrays/

更新

PS:可以在具有更好数据结构的 1 GB RAM 的单机上完成

使用优先级队列可以在小于 O(N) 空间 的情况下完成合并，即 O(K) 空间，即问题的核心。