algorithm - 如何将数据添加到一堆已排序的文件中

Question

如果之前重复过，我深表歉意，但我找不到任何符合我选择的措辞的帖子。我正在准备面试，并且一直在阅读有关外部分类的内容。例如，如果要对几个32位整数的硬盘进行排序，可以进行计数排序，使用64位计数器对32位整数进行计数。然后，对于每个可能的 32 位整数值，您都会有一个计数器来表示它。您还可以对类似的事情使用外部合并排序，花费 O(nlogn) 时间而不是 O(1) 时间。然而，我一直在考虑一个可能很常见的案例，但我想不出最好的方法——向可能跨越许多硬盘的一堆排序文件添加新数据。

如果内存中有数据，可以使用堆(优先级队列)在登录时间内完成此插入。但是，我们不能从硬盘空间中创建一个堆。对于列表，您将不得不使用 O(logn) 搜索来查找数据的位置(对于二进制搜索，已排序)，然后将其余数据向后或向前移动，或者您可能不必根据实现移动任何内容容器的(数组、链表等)。但是，在硬盘世界中，读取和写入比在 RAM 中昂贵得多，因此在某处插入数据然后移动(重写)其余数据似乎非常昂贵。你们有什么技巧可以推荐给我吗？我很乐意自己阅读，只是找不到正确的方式来表达我的问题以查找任何信息。谢谢!

Answer 1

我想说的是读​​出你排序数据的文件，读出你想要排序并添加到那里的文件，扣上计数器，然后用新计算的一个简单地覆盖排序数据文件。在现代磁盘系统上，直接读取比随机读取要便宜得多，而且您无论如何都需要为找到的每个 int 分配一个位置，因此对整个卷的单个顺序读取将比对单个扇区的约 32 次读取耗时更少每个要排序的文件数。

此外，我想说对 32 位整数进行排序最好用计数器形式的结果来完成，尤其是在像“几个硬盘”这样的超大规模时，你会期望几乎每个桶中至少有 1 个在 32 位空间中，因此存储 64 位 *2^32 可能比说 2^33 个 32 位零然后 2^32 个小...