sorting - 行的外部排序。要合并的文件数量？

Question

我需要在 PC 上以最短时间（数十 GB）对文件中的行进行排序。我应该使用 N 路归并排序，对吗？如何选择数字 N（一次要合并的文件数）？我应该在读取或写入和调整 N 时测量延迟吗？或者从系统中获取磁盘信息？如果我有 SSD，我可以一次合并所有排序的部分吗（程序需要以某种方式确定它是否是 SSD）？还可以进行哪些其他优化？

标签： sortingmergesortexternal-sorting

Answer 1

在创建一组排序子文件的初始传递之后，对于硬盘驱动器，通常使用使用最小堆的 16 路合并，这仍然足够快以保持进程 I/O 绑定。为了减少随机访问开销，需要大量的读/写，如果你有足够的内存（16 个输入块，1 个输出块，1.7GB 的缓冲区空间），则需要 100MB。

对于 SSD 更快的传输速率，小于 16 k 路的合并可能是最好的。对于读取速率为 2GB/S 且写入速率超过 1GB/S 的非常快的 SAS 或 NVMe SSD，在保持驱动器接近 I/O 限制的同时，可以在没有堆的情况下进行 2 路或 4 路合并。对于读写速率略高于 500MB/S 的 SATA SSD，6 到 16 路合并可能是最好的。