合并过程中的文件排序

我对一个主题感兴趣，假设我们有8个文件，每个文件包含10亿个整数，我们应该将这些文件合并成80亿个整数文件，每个文件中的所有文件都进行排序。当然，如果我们做8次合并，任务很简单，但是我的问题是，文件的重要排序是什么，我们应该在哪个顺序上进行组合？例如，在开始时，不是合并第一个和第二个文件，创建新的M文件并与第三个文件合并，也许有时候合并第二个和第三个文件，然后与第一个文件合并会更有利吗？我想我的问题很清楚。合并过程中的文件排序问题？如果是这样，我们如何选择最优的？合并过程中的文件排序

来源

2012-03-28 dato datuashvili

这可能是最佳做一个8路合并排序没有中间文件。打开8个文件句柄，找到所有8个最小的整数，将其写入输出文件并读取该文件中的下一个整数。您可能可以使用插入排序来管理8个源的8个元素的数组（持有文件句柄和读取的最后一个值）。

就排序而言，如果您一次只能合并两个文件，我可能会先合并最小的文件。简化你的例子，你可以看到为什么。

假设您有3个文件，其中有1,2和100条记录。
如果合并1 & 2与3所记录的临时文件，然后合并，与100，你已经阅读106条记录，并书面103
如果改为合并1 & 100转换成101个记录的临时文件，然后将其与2合并，您将读取204条记录并写入103.

来源

2012-03-28 20:57:41 tomlogic

合并过程中的文件排序

回答

相关问题