c - 是否可以映射一个非常大的文件并使用 qsort？

Question

我必须对大量无法放入内存的数据进行排序，而我知道可以做到这一点的一件事是“外部排序”。但我想知道是否可以映射这个大数据文件，并使用'qsort'，因为它是一个'普通数据数组'？如果这是可行的，那么与“外部排序”有什么区别？

Answer 1

如果该文件适合您地址空间中的连续映射，则可以执行此操作。如果它不会，你不能。

至于区别：

• 如果文件刚好适合，然后添加更多数据，则 mmap 将失败。正常的外部排序不会因为您有更多数据而突然停止工作。
• 如果您不使用 映射它MAP_PRIVATE，排序将改变原始文件。正常的外部排序不会（必然）
• 如果你用 映射它MAP_PRIVATE，如果虚拟机没有空间复制整个文件，你可能随时崩溃。同样，严格外部排序的内存需求不会随数据大小线性扩展。

---

tl;博士

有可能，它可能会以不可预测和不可恢复的方式失败，您几乎肯定不应该这样做。

Answer 2

如果数据适合地址空间，它肯定可以工作（几乎可以肯定在 64 位机器上可以；可能在也可能不在 32 位机器上），但性能很大程度上取决于所使用的底层算法qsort及其数据局部性属性. 要考虑的一个问题是元素的数量是否很大，或者每个元素在磁盘上是否很大。在后一种情况下，您最好执行mmap，但为每个元素分配一个单独的指针数组，然后使用比较函数对指针数组进行排序，比较它们指向的内容。这将大大减少数据在内存中移动的次数，但如果要将输出存储回同一个文件，最后需要做一些工作。

Answer 3

是的，只要您在文件中有固定长度的记录并且文件适合一系列连续的 VM 地址，这是可能的，实际上这可以被认为是外部排序的一种幼稚方法。不过，它可能不是城里最快的算法，因为qsort不会针对这个用例调整实现。