c++ - 面试谜题: Sorting a million number input with limited memory

Question

我尝试使用外部排序来回答这个问题，但面试官回答说复杂度很高 n.n(log(n)) 即 n 平方 *logn。有没有更好的选择。

为了简化问题:假设我们有 1000 个元素需要排序，空间只分配给 100 个元素。比外部排序花费更少时间的最佳算法是什么。

Answer 1

我不知道你(或面试官)指的是哪种外部类型，但是

我的建议是 10 路(在你的情况下)合并:

• 将文件分成 MAX_MEM 大小的 block (100 个元素)
  • 这是O(1)
• 对内存中的每个 block 进行排序并存储为一个单独的文件
  • 这是 O((n/max_mem) * (max_mem) log(max_mem))) = O(n log(max_mem))
• 将所有 block 作为元素流打开
• 通过在每一步选择最低元素来合并所有流。
  • 这是 O(n log(n/max_mem)) 使用 minHeap 或 O(n^2/max_mem) 平凡(在实践中可能更快)
• 删除 block

关于计算，这是 O(n (log(max_mem)+log(n/max_mem)))=O(n log(n))

关于磁盘 I/O，如果所有合并都在一次传递中完成，这就是2*n 读取和2*n 写入只有。更一般地，它是 (1+[合并树的深度])*n

所有写入都是顺序的。第一个读取是顺序的，第二个是顺序的，从 10 个文件中交错读取。

如果有更多数据，则需要重复或递归合并(每个 block 100 个，然后重复选择 N 个 block )。此时，值得将拆分+排序步骤替换为替换/选择，如@amit 的回答中所述，尤其是当数据几乎已经排序时(您可以完全避开合并步骤)。

请注意，较高的 N 可能会增加计算量(非常轻微，如果您使用正确的结构)，但会显着减少磁盘 I/O 的数量(达到一定数量；如果您一次合并太多 block ，您可能读取缓冲区的内存不足，导致不必要的读取)。磁盘 I/O 很昂贵，但 CPU 周期不是。