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

Question

目前我正在尝试将大量数据写入文件，

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

当我生成我的数据时，结构被创建并按数量顺序写入文件。但我需要按 ID 对数据进行排序。

记得有 6gb 的数据，我如何根据 ID 值对这些结构进行排序然后写入文件？

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

我有点卡住了，因为我想把它保存在一个数组中，但显然这个数据量太大了。

我需要一种对大量数据进行排序的好方法吗？ (6GB)

Answer 1

我还没有找到对此问题有真正基本答案的问题，所以这里开始吧。

如果你在 64 位机器上，顺便说一下，你应该认真考虑将所有数据写入一个文件，内存映射文件，并使用你喜欢的任何数组排序。 Quicksort 对缓存非常友好:它不会出现严重问题。该作业可能旨在阻止您这样做，但可能有点过时了 ;-)

否则，您需要某种外部排序。还有其他方法可以做到这一点，但我认为合并排序可能是最简单的。在开始合并之前:

• 计算出内存中可以容纳多少数据(或者再次映射)。如果您使用的是 PC，那么 1GB 似乎是一个合理的假设，但它可能会多几倍或少几倍。
• 加载这么多数据(在示例中是您的 6 个文件之一)
• 对其进行快速排序(因为您标记为“快速排序”，我猜您知道该怎么做)，或者您选择的任何其他排序方式。
• 将其写回磁盘(如果您没有进行 mmap)。

这为您留下了 6 个 1GB 的文件，每个文件都单独排序。在这一点上，您可以逐步进行，也可以一次完成。对于 6 个 block ，在所谓的“6 向合并”中进行全部处理就可以了:

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

关于如何计算出 6 种可能性中哪一种可能性最小，您可以进行一些优化，但最大的性能差异将是确保您使用足够大的读写缓冲区。

显然，6 向合并并没有什么特别之处。如果您宁愿坚持更容易编码的双向合并，那么您当然可以。合并6个文件需要5次双向合并。