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

Question

这个问题看似简单,但我无法理解它背后的真正工作.我知道人们会说,分解成512 Megs块并将它们排序,就像使用Map reduce一样使用Merge Sort.

所以这是我的实际问题:

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

在合并结束时我将能够将两个0.5 TB的块与另一个0.5 TB的块合并.虚拟内存的概念是否会在这里发挥作用？

我在这里澄清我的基础知识,我希望我正确地问这个非常重要的问题(正确).另外,谁应该做这个合并(排序后)？我的机器或那些2000机器中的一些？

Answer 1

你如何合并的简短版本是这样的:

1)您为要合并的每台计算机创建一个包含一个插槽的表.

2)你问每台机器他们还没有给你的最低入口.

3)从表中删除最低值的条目,输出它,并要求该机器用它尚未给你的最低条目重新填充慢速,如果机器没有条目,则将插槽留空.

4)重复步骤3直到表为空.

这允许您从N个机器合并,一次只存储N个条目.当然,您可以轻松优化它以保存每台机器的M个条目.在这种情况下,您需要存储N*M个条目,当一个插槽为空时,向该机器询问M个条目以重新填充它.

Answer 2

这是一种应该有效的理论方法。假设您有 2000 个 512mb 文件，准备创建一个 1TB 文件。

如果您只是循环遍历每个文件，找到哪个文件的 FIRST 值最低，然后将其移动到目标文件中，然后重复，那么您最终将按顺序得到所有内容。RAM 使用量应该很小，因为您永远不需要一次打开多于一行。

显然你应该能够对此进行优化 - 将每个文件的第一行保留在 RAM 中，并且速度应该会更快一些。

Answer 3

这个问题可以简化为一个简单的问题。该问题旨在迫使您采用某种方法。这里是：

• 拾取大块=〜1GB，将它们分类并存储为单独的分类文件。
• 您最终在文件系统上获得1000个1GB排序的文件。

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

  合并k个排序的数组需要您一次维护一个最小堆（优先级队列），其中有k个元素。

也就是说，在我们的例子中，k = 1000（文件）。（1GB的ram可以存储1000个数字）

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

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

请参阅：http : //www.geeksforgeeks.org/merge-k-sorted-arrays/

更新资料

PS：可以在具有1 GB RAM和更好数据结构的单台计算机上完成

可以在少于O（N）空间的情况下进行合并，并使用Priority Queue，即O（K）空间，即问题的核心。