如何在大型输入集中更快地在C中进行这种排序程序

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

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中预定义)也会更快,应该如何应用于上面的代码?

您询问了基于文件键的排序问题,并给出了有关如何在内存中排序的各种答案。 您添加了一个补充问题作为答案,然后创建了这个问题(这是正确的)。

这里的代码基本上是基于磁盘的冒泡排序,具有O(N 2 )复杂性,并且由于它操纵文件缓冲区和磁盘而导致时间性能不佳。 在最好的时候,冒泡排序是一个糟糕的选择 – 简单,是的,但很慢。

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

  1. 如果可能,将所有数据读入内存,在内存中排序,并将结果写出。
  2. 如果它不能全部适合内存,请尽可能多地读入内存,对其进行排序,并将排序后的数据写入临时文件。 根据需要重复以对所有数据进行排序。 然后将临时文件合并到一个文件中。 如果数据集真的是天文数字(或内存真正微不足道),则可能必须创建中间合并文件。 但是,现在,即使在32位计算机上,您也必须排序数百GB才能成为问题。
  3. 确保选择一个好的排序算法。 通过适当的枢轴选择进行快速排序非常好。 你也可以查看’introsort’。

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

您将在将多个已排序文件合并到一个文件的答案中找到合并代码的示例。 合并代码在其合并模式中超出系统sort程序,这很有趣,因为它不是高度优化的代码(但它合理地工作)。

你可以看看软件工具中描述的外部排序程序,虽然它有点深奥,因为它是用’RatFor’或Rational Fortran编写的。 但是,该设计很容易转移到其他语言。

是的,无论如何,请使用qsort()。 使用它作为SpiderPig建议通过将整个文件读入内存,或者作为内存排序,适用于准备合并排序的内存。 不要担心最糟糕的表现。 一个不错的实现将采用中位数(第一个,最后一个,中间)来对已经排序和逆序的病态情况进行快速排序,并在随机情况下获得更好的平均性能。

这个全内存示例向您展示了如何使用qsort:

 #include  #include  #include  typedef struct record_tag { int key; char data[12]; } record_type, *record_ptr; const record_type * record_cptr; void create_file(const char *filename, int n) { record_type buf; int i; FILE *fptr = fopen(filename, "wb"); for (i=0; ikey > b->key) - (a->key < b->key); } /* Read an input file of (record_type) records, sort by key field, and write to the output file */ void sort_file(const char *ifname, const char *ofname) { const size_t MAXREC = 10000; int n; FILE *ifile, *ofile; record_ptr buffer; ifile = fopen(ifname, "rb"); buffer = (record_ptr) malloc(MAXREC*sizeof *buffer); n = fread(buffer, sizeof *buffer, MAXREC, ifile); fclose(ifile); qsort(buffer, n, sizeof *buffer, compare_records); ofile = fopen(ofname, "wb"); fwrite(buffer, sizeof *buffer, n, ofile); fclose(ofile); } void show_file(const char *fname) { record_type buf; int n = 0; FILE *fptr = fopen(fname, "rb"); while (1 == fread(&buf, sizeof buf, 1, fptr)) { printf("%9d : %-12s\n", buf.key, buf.data); ++n; } printf("%d records read", n); } int main(void) { srand(time(NULL)); create_file("test.dat", 99); sort_file("test.dat", "test.out"); show_file("test.out"); return 0; } 

注意compare_records函数。 qsort()函数需要一个接受void指针的函数,因此必须将这些指针强制转换为正确的类型。 然后模式:

 (left > right) - (left < right) 

...如果左参数更大,则返回1;如果相等则返回0;如果右参数更大,则返回-1。

可以改进。 首先,绝对没有错误检查。 这在生产代码中并不明智。 其次,您可以检查输入文件以获取文件大小,而不是猜测它小于某个MAXxxx值。 一种方法是使用ftell 。 (按照文件大小示例的链接进行操作。)然后,使用该值分配单个缓冲区,其大小足以对数据进行排序。

如果没有足够的空间(如果malloc返回NULL),那么你可以回退到适合内存的排序块(使用qsort,如在代码片段中),将它们写入单独的临时文件,然后将它们合并为单个输出文件。 这更复杂,而且很少,因为有专门为排序大文件而设计的排序/合并实用程序。