如何优化合并排序？

Question

我有两个1 GB的文件，每个文件只包含排序顺序的数字。现在我知道如何读取文件的内容并使用合并排序算法对其进行排序并将其输出到另一个文件中，但我感兴趣的是如何使用100MB缓冲区大小（我不担心划痕空间）。例如，一种方法是从两个文件中读取50 MB的块并对其进行排序，并在排序后，我可以读取一个新元素并继续这个过程，直到两个文件结束（任何人都可以给我任何想法如何实现这个）。

Answer 1

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

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

您只需要一个条件来检查您的某个缓冲区是否为空。如果是，则从缓冲区关联的文件中读取更多内容。

Answer 2

您可能想要以合理的块读/写以避免I/O开销。因此可能使用〜30M，input1，input2和output三个缓冲区。

继续下去，直到任一输入缓冲区为空或输出缓冲区已满，然后读/写以填充/清空空/满缓冲区。

这样你就可以从磁盘写入/读取大块数据。

除此之外，在进行排序时，您需要异步I/O来读取/写入数据。但这可能是矫枉过正。

Answer 3

由于您只进行合并，而不是完整的排序，它只是基本的合并循环。纯粹的顺序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，这是文件系统非常擅长的。你写一个简单的循环来从文件中读取像byte或int这样的小单元，然后将它写入另一个单元。只要你试图读取一个字节，系统就会分配一个漂亮的大缓冲区，将一大块文件划入缓冲区，然后将字节从缓冲区中送出。它会一直这样做，直到你需要另一个缓冲区，当它无形地为你另一个缓冲区时。您正在编写的文件会发生同样的事情。现在CPU非常快，所以它可以遍历输入字节，将它们复制到输出中，只需要读取或写入缓冲区的一小部分时间，因为读取或写入速度不会快于外部硬件。更大的缓冲区可以提供帮助的唯一原因是，读/写时间的一部分就是所谓的“延迟”，基本上是将磁头移动到所需磁道所需的时间，并等待所需的扇区出现。大多数文件系统将文件分解为散布在磁盘周围的块，所以头部仍在跳动。你可以听到它。

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

当然，如果你可以安排它，以便读取和写入的文件都是在单独的物理磁盘驱动器和驱动器不分段多，那么头部运动的量能被最小化，更大的缓冲区可能会有所帮助。但基本上，通过一个简单的程序，您几乎可以期待简单的代码像磁盘可以移动数据一样快，而巨大的缓冲区可能会有所帮助，但不是很多。

Answer 4

为什么不使用标准库？

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

Answer 5

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