如何在c中对大量数据进行排序？

Question

目前我正在尝试将不真实的数据写入文件,

基本上我生成一个新的数据结构并将其写入文件,直到文件变为1gb大,这发生在6个文件中,每个1gb,结构很小.8个字节长,有两个2变量id和amount

当我生成我的数据时,将按照金额的顺序创建结构并将其写入文件.但我需要按ID排序的数据.

记得有6gb的数据,我怎么能用id值对这些结构进行排序然后写入文件？

或者我应该首先写入文件,然后对每个单独的文件进行排序,以及如何将所有这些数据合并到一个文件中？

我有点卡住了,因为我想把它放在一个数组中,但显然这个数据量太大了.

我需要一个很好的方法来排序很多数据？(6GB)

Answer 1

我没有找到一个关于此的真正基本答案的问题,所以这里有.

顺便提一下,如果您使用的是64位计算机,则应认真考虑将所有数据写入文件,映射文件的内存,并使用您喜欢的任何数组排序.Quicksort非常适合缓存:它不会严重破坏.该任务可能旨在阻止你这样做,但可能有点过时;-)

如果做不到这一点,你需要某种外部排序.还有其他方法可以做到,但我认为合并排序可能是最简单的.在开始合并之前:

• 计算出你可以装入内存的数据量(或者,再次,mmap).如果你在PC上,那么1GB似乎是一个公平的假设,但它可能是或多或少的几倍.
• 加载这么多数据(所以你的6个文件中的一个,在这个例子中)
• 快速排序(因为你标记了"quicksort",我想你知道该怎么做),或者你选择的任何其他类型.
• 把它写回磁盘(如果你没有mmap).

这将为您留下6个1GB文件,每个文件都是单独排序的.此时,您可以逐步进行操作,也可以一次性完成所有操作.有6个块,整个很好,在所谓的"6路合并":

• 打开文件进行写作
• 打开你的6个文件进行阅读,并从每个文件中读取几百万条记录
• 检查6个缓冲区中每个缓冲区的6个记录.其中一个6必须是最小的.将其写入输出,然后向前一步通过该缓冲区.
• 当您到达每个缓冲区的末尾时,请从正确的文件中重新填充它.

关于如何计算出6种可能性中最小的可能性,您可以做一些优化,但性能差异很大,确保使用足够大的读写缓冲区.

显然,合并是6路没什么特别的.如果你宁愿坚持双向合并,这更容易编码,那么你当然可以.合并6个文件需要5次双向合并.