如何优化归并排序？

StackOverflow https://stackoverflow.com/questions/3814188

题

我已经1 GB的两个文件的每个仅包含按排序顺序号。现在我知道如何读取文件的内容和排序它们使用合并排序算法，并输出到另一个文件，但我感兴趣是如何做到这一点只使用100MB缓存大小（我不担心划痕空间）。例如，一个方法是从两个文件读取50个MB数据块和排序它，因为它是排序我能读一个新的元素，并继续过程，直到我到了这两个文件的结尾（任何人都可以给我任何的想法如何实现这一点）。

有帮助吗？

解决方案

听起来像你只需要为合并的数字在你的文件，而不是那种他们，因为他们是在每个文件已经排序。 合并的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

现在你可以从两个文件读取的第一个50 MB编号的两个缓冲区，应用合并算法，那么当缓冲器中的一个已经被耗尽（所有的数字分析），读取所需要的文件，另外50 MB 。有没有必要进行排序任何东西。

您只需要一个条件，即检查时，您的缓冲区之一是空的。当是时，从该缓冲器与相关联的文件中读出更

其他提示

为什么不利用标准库？

#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);
}

您可能想阅读的合理块/写，以避免I / O开销。 因此，可能使用的〜30M，输入1，输入2和输出三个缓冲器。

请下去，直到在输入缓冲器中的任一个是空的或输出缓冲器是满的，则读/写填充/排空空/满缓冲器。

你正在写/从磁盘读取数据的大块这样。

除此之外需要异步I / O读/写数据，而你正在做的排序。但是，这可能是矫枉过正。

由于您只是做了合并，而不是一个完整的排序，它只是基本的合并循环。纯顺序I / O。无需有关缓冲区的担心。想象一件外套拉链。就这么简单。 （注意：这可能是快了很多，如果数字是在文件的二进制格式不仅将文件较小，但该计划将是I / O限制，而数字将是完全准确）

double GetNumberFromFile(FILE file){
  if (feof(file)){
    return BIGBIGNUMBER;
  }
  else {
    return ReadADouble(file);
  }
}

double A = GetNumberFromFile(AFILE);
double B = GetNumberFromFile(BFILE);
while (A < BIGBIGNUMBER && B < BIGBIGNUMBER){
  if (A < B){
    write A;
    A = GetNumberFromFile(AFILE);
  }
  else if (B < A){
    write B;
    B = GetNumberFromFile(BFILE);
  }
  else {
    write A;
    write B; // or not, if you want to eliminate duplicates
    A = GetNumberFromFile(AFILE);
    B = GetNumberFromFile(BFILE);
  }
}
while (A < BIGBIGNUMBER){
    write A;
    A = GetNumberFromFile(AFILE);
}
while (B < BIGBIGNUMBER){
    write B;
    B = GetNumberFromFile(BFILE);
}

在回答你的问题，考虑一个简单的问题，一个文件复制到另一个。你只是在做顺序I / O，该文件系统是真的很好。你写一个简单的循环来读取小单位，比如从文件中的字节或INT，并将其写入到另一个。只要你尝试读取一个字节，系统分配一个漂亮的大缓存，挥笔文件到缓冲区的一大块，再喂你的字节移出缓冲区。它使这样做，直到你需要另一个缓冲区，当它无形中gloms另外一个你。同样的事情发生与你正在写的文件。现在的CPU是相当快，因此它可以通过输入字节迭代，将它们复制到输出，在需要读取或写入一个缓冲的时间的一小部分，因为读取或写入不能再比快外部硬件。更大的缓冲区将有助于唯一原因是阅读的一部分/写时间是什么所谓的“潜伏”，基本上采取的磁头移动到想要的曲目，并等待所需的部门来左右的时间。大多数文件系统打破了文件转换为在磁盘周围洒块，所以头反正跳。你可以听到它。

复制和合并算法像你是它的读取两个文件，而不是一个之间的唯一区别。无论哪种方式，基本时间序列的一系列缓冲器的读取和写入与CPU动作少量散布。 （这是可以做到的重叠的I / O，从而使CPU动作发生的，而的的I / O发生的，所以基本的没有缓冲器之间延迟读取和写入，但它是一个更大的交易时的CPU是慢1000倍。）

当然，如果你可以安排它，以便读取文件并写入都在不同的物理磁盘驱动器和驱动器没有太大的碎片，然后头部运动的量可以最小化，并且更大的缓冲区可能帮助。但基本上，有一个简单的程序，你几乎可以指望简单的代码去一样快盘可以将数据和巨缓冲区也许会有帮助，但并不多。

基准。读值按值和块读取。感到不同！ =）

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top