如何优化合并排序？
如何优化合并排序？
提问于 2010-09-28 23:09:32
我有两个1 GB的文件，每个文件只包含排序顺序中的数字。现在我知道如何读取文件的内容，并使用合并排序算法对它们进行排序，并将其输出到另一个文件中，但我感兴趣的是如何只使用100MB的缓冲区大小(我不担心临时空间)。例如，一种方法是从两个文件中读取50MB的块并对其进行排序，当它排序时，我可以读取一个新的元素，并继续这个过程，直到我到达两个文件的末尾(谁能告诉我如何实现这一点)。
回答 5
Stack Overflow用户
回答已采纳
发布于 2010-09-28 23:16:37
听起来你只需要对文件中的数字进行合并和排序，而不是对它们进行排序，因为它们已经在每个文件中进行了排序。merge sort的merge部分是这样的：
function merge(left,right)
var list result
while length(left) > 0 or length(right) > 0
if length(left) > 0 and length(right) > 0
if first(left) ≤ first(right)
append first(left) to result
left = rest(left)
else
append first(right) to result
right = rest(right)
else if length(left) > 0
append left to result
break
else if length(right) > 0
append right to result
break
end while
return result现在，您只需从两个缓冲区中的两个文件中读取前50MB的数字，应用合并算法，然后当其中一个缓冲区耗尽时(分析其所有数字)，从所需的文件中读取另一个50MB。没有必要对任何东西进行排序。
您只需要一个条件来检查其中一个缓冲区是否为空。如果是，则从与buffer关联的文件中读取更多内容。
Stack Overflow用户
发布于 2010-09-29 03:03:31
为什么不使用标准库呢？
#include <fstream>
#include <iterator>
#include <algorithm>
int main()
{
std::ifstream in1("in1.txt");
std::ifstream in2("in2.txt");
std::ofstream ut("ut.txt");
std::istream_iterator<int> in1_it(in1);
std::istream_iterator<int> in2_it(in2);
std::istream_iterator<int> in_end;
std::ostream_iterator<int> ut_it(ut, "\n");
std::merge(in1_it, in_end, in2_it, in_end, ut_it);
}Stack Overflow用户
发布于 2010-09-28 23:17:15
您可能希望以合理的块进行读/写，以避免I/O开销。所以可以使用大约30M的三个缓冲区: input1、input2和output。
继续执行，直到其中一个输入缓冲区为空或输出缓冲区已满，然后读/写以重新填充/清空空/满缓冲区。
这样，您就可以从磁盘中写入/读取大量数据。
除此之外，在进行排序时，您需要异步I/O来读/写数据。但这可能有点过头了。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/3814188
复制相关文章
相似问题
腾讯云开发者
