c - 如何使 C 中的排序程序对于大型输入集更快

Question

对于非常大的输入文件数据，此排序代码会失败，因为它需要很长时间才能完成。

rewind(ptr);
j=0;
while(( fread(&temp,sizeof(temp),1,ptr)==1) &&( j!=lines-1)) //read object by object
{
  i=j+1;
  while(fread(&temp1,sizeof(temp),1,ptr)==1)  //read next object , to compare previous object with next object 
   {
       if(temp.key > temp1.key)   //compare key value of object 
           {
            temp2=temp; //if you don't want to change records and just want to change keys use three statements temp2.key =temp.key;
            temp=temp1;
            temp1=temp2;
            fseek(ptr,j*sizeof(temp),0);        //move stream to overwrite 
            fwrite(&temp,sizeof(temp),1,ptr);   //you can avoid above swap by changing &temp to &temp1 
            fseek(ptr,i*sizeof(temp),0);        //move stream to overwrite
            fwrite(&temp1,sizeof(temp),1,ptr);  //you can avoid above swap by changing &temp1 to &temp
           }
    i++; 
   }
  j++; 
  fseek(ptr,j*sizeof(temp),0);  
}

关于如何使此 C 代码更快的想法？另外，使用 qsort()(在 C 语言中预定义)会更快吗？应该如何应用于上述代码？

Answer 1

你问了这个问题 Sorting based on key from a file并得到了关于如何在内存中排序的各种答案。您添加了一个补充问题作为答案，然后创建了这个问题(这是正确的)。

这里的代码基本上是基于磁盘的冒泡排序，复杂度为 O(N²)，时间性能很差，因为它正在操作文件缓冲区和磁盘。冒泡排序在最好的时候是一个糟糕的选择——简单，是的，但是很慢。

加速排序程序的基本方法是:

1. 如果可能，将所有数据读入内存，在内存中排序，然后将结果写出。
2. 如果不能全部放入内存，请尽可能多地读入内存，对其进行排序，然后将排序后的数据写入临时文件。根据需要经常重复以对所有数据进行排序。然后将临时文件合并为一个文件。如果数据集确实是天文数字(或者内存真的很小)，您可能必须创建中间合并文件。不过，如今，即使在 32 位计算机上，您也必须对数百 GB 的数据进行排序，这才成为一个问题。
3. 确保您选择了一个好的排序算法。使用适当的枢轴选择进行快速排序非常好。您也可以查找“introsort”。

您将在交叉引用问题(您的原始问题)的答案中找到示例内存排序代码。如果您选择编写自己的排序，您可以考虑是否将接口(interface)基于标准 C qsort() 函数。如果你写一个快速排序，你应该看看 Quicksort — Choosing the pivot答案有大量引用。

您将在 Merging multiple sorted files into one file 的答案中找到示例合并代码.合并代码在其合并模式下优于系统 sort 程序，这很有趣，因为它不是高度抛光的代码(但它相当熟练)。

您可以查看 Software Tools 中描述的外部排序程序，虽然它有点深奥，因为它是用“RatFor”或 Rational Fortran 编写的。不过，该设计很容易转移到其他语言。