将多个txt文件合并为一个

Question

下午好。

我遇到了一些问题。我可以解决这个问题，但我在编程方面没有什么经验，在我看来，这个问题有一个更漂亮、更合理的解决方案。

问题如下。给定一组总大小超过100 of的文本文件。从2到N的文件数包含排序的唯一编号(例如ID)。它希望将所有数字合并到一个输出文件中。在结果文件中，还需要对文件号进行排序。

我将按以下方式解决这个问题:打开所有文件。取出每个文件的第一个号码。把它们放在容器里(如向量)。在容器中找到最小的数字。将最小数目放入输出文件中。在他的位置上，从文件中输入以下数字，从文件中取下最小的数字。该方法似乎称为“外部合并排序”。

请告诉我，有没有更聪明的方法来解决这个问题？

Answer 1

外部并购正是针对这一问题而产生的。这类的复杂性是N* log(number_of_files)。

为了简化代码，您可以将filestream和数字一起存储在优先级队列中。

完全未经测试，但可能有帮助的代码：

std::vector<ifstream> file_streams(stream_count);  
// open streams.
using int_and_stream = std::pair<int, std::ifstream&>;
using cont = std::vector<int_and_stream>;
std::priority_queue<int_and_stream, cont, pair_comparer> queue;

for(auto& stream: file_streams){
   int id;
   stream >> id;
   queue.push(std::make_pair(id, stream));
}

while(!queue.empty()){
   auto smallest = queue.top();
   outstream << smallest.first;
   int id;
   if(smallest.second >> id){ // file ended?
      queue.push(std::make_pair(id, stream));
   }
}              

对于pair_comparer，您可以查看here

Answer 2

你的方法很好。

但是你可以有一个排序向量的数字/文件对，所以你会花更少的时间来寻找最小的数字，因为在去掉最小的条目之后，你可以读取下一个值，然后用比线性排序更有效的算法将它插入数组中。当您有大量的输入文件时，这是更有效的。

但是，假设I/O的成本比数字比较高得多，这种方法是可以的。

Answer 3

更好的方法是将每个文件的当前头存储在优先级队列中。然后，在每个步骤中，取优先级队列的顶部(注意该项目来自的输入文件)，将其写入输出文件，并将该输入文件的下一项推入优先级队列。