logo标签列表

使用只有1GB RAM的计算机对1TB文件进行排序

c++sortingmemory-managementexternal-sorting
12
这个问题看起来很简单，但我不明白它背后的真正工作原理。我知道人们会说，将文件分成512兆字节的块，然后使用Map Reduce像使用归并排序一样对它们进行排序。
那么这就是我的实际问题：假设我将文件分成512兆字节的块，然后发送到不同的主机上进行排序。假设这些机器使用了归并排序。现在假设我有2000台机器，每台机器都对2000个512兆字节的块进行了排序。现在当我合并它们时，这怎么工作呢？大小不会继续增加吗？例如，合并两个512兆字节的块将使其变为1024兆字节，这是我的RAM的大小，所以这该怎么办呢？任何机器都无法将超过512兆字节的块与另一个块合并，因为这样会超过1 GB。
在合并结束时，我如何能够将两个0.5 TB块合并到另一个0.5 TB块中。虚拟内存的概念是否涉及其中？
我在这里澄清我的基础知识，我希望我正在正确地提出这个非常重要的问题。此外，谁应该执行这个合并（在排序之后）？我的计算机还是这2000台机器中的一部分？
只有在尝试将文件保留在内存中时，才会耗尽内存。一旦您将文件分块并对每个块进行排序，您只需要在将它们合并/写入新文件时在内存中保留每个文件的一行即可。 - Marc B
归并排序是我最喜欢的算法之一。它非常简单易懂，而且非常有用。 - Mark Ransom
顺便提一下，只需对整个数据集进行2次读/写操作即可完成此操作（总共4 TB的I/O）。我会跳过细节，因为它非常复杂，但它使用与外存FFT算法相同的方法。 - Mysticial
你应该考虑使用更好的数据结构。 - Yugal Jindle
5个回答
10
这个问题可以简化为一个更简单的问题。这个问题的设计是为了强制你采取一种方法。下面是具体步骤：
- 挑选大小约为1GB的块，排序并将它们作为单独的已排序文件存储。 - 最终会在文件系统上得到1000个1GB已排序文件。 - 现在，只需要将k个已排序数组合并成一个新数组。 - 合并k个已排序数组需要维护一个最小堆（优先队列），每次维护k个元素。
即 k = 1000（文件）在我们的情况下。（1GB内存可以存储1000个数字）
因此，不断从优先队列中弹出元素并保存到磁盘中。
你将获得一个新的1TB大小的已排序文件。
参考：http://www.geeksforgeeks.org/merge-k-sorted-arrays/ 更新

PS：可以在具备更好的数据结构的情况下，在一台1GB RAM的机器上完成。

使用优先队列即可在小于O(N)空间的情况下进行合并，即O(K)空间，也就是问题的核心所在。

非常清晰且良好的解释。我之前对解决方案有些困惑。 - Al-Alamin
6
如何合并的简短版本如下：
1）创建一张表，其中每个插槽都对应一个要合并的机器。
2）向每台机器请求它们尚未提供给您的最低条目。
3）从表中删除最小值的条目，输出它，并要求该机器用其未提供的最小条目重新填充插槽，如果机器的条目已经用尽，则留下插槽为空。
4）重复步骤3，直到表为空为止。
这样可以通过同时只存储N个条目来从N台机器上进行合并。当然，您可以轻松地将其优化为每台机器存储M个条目。在这种情况下，您需要存储N*M个条目，并在插槽为空时向该机器请求M个条目以进行重新填充。
谢谢David，我的问题有点不同。抱歉，我应该用更好的方式提问。但是“In Silico”的答案解决了我所有的疑惑。 - bruceparker
6
这里有一种理论上可行的方法。假设你已经准备好了2000个512mb的文件，想要创建一个1TB的文件。
如果你只是循环遍历每个文件，找到具有最低FIRST值的文件，然后将其移动到目标文件中，并重复这个过程，那么最终你会得到所有文件按顺序排列的结果。由于你永远不需要同时打开超过一行，所以RAM使用应该非常小。
显然，你可以进行优化 - 在处理过程中保留每个文件的第一行，这样速度应该会更快。
被30秒打败 - 听起来@David Schwartz有相同的解决方案，但还附带了一个编号列表的奖励。 - SpoonNZ
1
存在更好的解决方案。 - Yugal Jindle
每个文件必须已经排序，以便轻松找到最低的第一个值。 - Sunil Ajagekar
4
现在假设我有2000台机器，每台机器有2000个已排序的512兆块。现在当我将它们合并回去时，这该怎么办？大小不会再次增加吗？例如，合并两个512兆将使1024兆，这是我的RAM大小，那么这怎么工作？任何机器都无法将大于512兆块的块与另一个块合并，因为然后大小> 1 GB。
实际的归并排序实现方式并非如此。归并排序（以及相关的排序算法）的好处在于您不需要将整个数据集保存在内存中才能使其正常工作。在合并时，您只需要一次读取文件的一小部分到内存中，然后很快将其写出。
换句话说，您不需要随机访问来进行归并排序。如果没有这种好的属性，使用当时可用的技术在磁带驱动器上对数据进行排序将是不可能的。磁带驱动器当然不是随机访问媒体，而且当时的RAM是以千字节为单位衡量的。
假设我正在处理两个0.5TB的块。现在，我知道它们的第一行是最小的（假设按字符串长度排序）。因此，在内存中，我只有每个文件的前两行和其余部分在内存中？ - bruceparker
不，你只需要将两个文件的前几行读入内存进行比较，然后将较小的写入第三个文件。虽然在实际实现中，由于磁盘I/O速度较慢，你会尝试一次性读取尽可能多的数据，但大部分时间数据都在磁盘上。 - In silico
1
归并排序的好处在于不需要随机访问，顺序访问就可以了。这使得它成为数据集太大无法放入内存时的完美解决方案。
单个归并操作需要2个（或更多）输入，并产生一个输出。您只需将输入组合成输出，直到只剩下一个文件即可。
谢谢Mark。在阅读“In Silico”的回答后，我的思路变得更加清晰了。你们太棒了。谢谢。我还有这个问题吗？所以假设我正在处理两个0.5TB的块。现在，我知道它们的第一行是最小的（假设按字符串长度排序）。那么在内存中，我只需要保存每个文件的前两行和其余部分？ - bruceparker
@Leoheart，我想你的意思是“文件的其余部分在磁盘上”。如果是这样，你是正确的。 - Mark Ransom
哦，抱歉。是的，我指的是磁盘上文件的其余部分。 谢谢。 - bruceparker
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接