我在 64 位 Linux 机器上使用 gcc 4.7.2。
我有 20 个已排序的大型二进制 POD 文件，我需要将它们作为外部合并排序中最终合并的一部分进行读取。
通常，我会mmap读取所有文件并使用 amultiset<T,LessThan>来管理从小到大的合并排序，然后再mmap写入磁盘。
但是，我意识到，如果我std::mutex对这些文件中的每一个都保留 a，我可以创建第二个线程来向后读取文件，并同时从大到小排序。如果我事先决定第一个线程将恰好采用 n/2 个元素，而第二个线程将采用其余元素，那么我将不需要在事物的输出端使用互斥锁。
在这种特殊情况下，平均而言，可能会发生读锁争用，可能会发生 20 次，所以这是可以接受的。
现在，这是我的问题。在第一种情况下，很明显我应该调用madvisewith MADV_SEQUENTIAL，但我不知道在第二种情况下我应该做什么，我正在向后读取文件。
我MADV_REVERSE在手册页中没有看到。我应该使用MADV_NORMAL还是根本不打电话madvise？
回想一下，当数据量大到无法放入内存时，就需要进行外部排序。所以我们剩下一个更复杂的算法来使用磁盘作为临时存储。分而治之的算法通常涉及分解数据、进行部分排序，然后合并部分排序。
我的外部合并排序步骤
- 取 n=10 亿个随机数并将它们分成 20 个大小相等的碎片。
- 将每个分片从小到大单独排序，并将每个分片写入自己的文件。
- 打开 40 个 mmap，每个文件 2 个，前进一个，后退一个，每个文件关联一个互斥体。
std::multiset<T,LessThan> buff_fwd;为正向线程实例化 a ，std::multiset<T,GreaterThan> buff_rev为反向线程实例化 a。有些人更喜欢在这里使用优先级队列，但本质上，插入排序容器将在这里工作。- 我喜欢称这两个缓冲区为表面和底部，表示尚未添加到最终排序中的最小和最大数字。
- 从分片中添加项目直到 n/2 用完，然后在另一个线程中使用 mmap 从开始到中间，从末端到中间将分片刷新到一个输出文件。您基本上可以随意刷新，但至少应该在任一缓冲区占用过多内存之前执行此操作。