1

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

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

4

3 回答 3

5

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

我的建议是 10 路（在您的情况下）合并：

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

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

关于磁盘 I/O，如果所有的合并都是一次性完成的，那么这就是2*nreads only 和2*nwrites only。更一般地说，它是(1+[depth of the merge tree])*n

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

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

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

于 2012-12-08T08:31:13.877 回答
3

也许面试官希望你问：这些号码是 J. Bentley （Cracking the Oyster）提到的唯一七位数电话号码吗？

于 2012-12-08T09:05:33.687 回答
3

这样做的标准方法是外部排序。

在外部排序中 - 不仅具有O(nlogn)复杂性很重要 - 尽可能减少磁盘读取/写入，并使最多的读取和写入顺序（而不是随机）也很重要 - 因为磁盘访问效率更高当按顺序完成时。

这样做的标准方法确实是 k-way 合并排序，正如@JanDvorak 所建议的那样，但是我打算纠正的建议有一些错误和补充：

  1. 首先，对输入进行RS（替换选择）会减少初始“运行”的次数（递增序列的数量），因此通常会减少后期合并排序所需的迭代总数。
  2. 我们需要内存来缓冲（读取和写入输入） - 因此，对于内存大小 M 和文件大小 M*10，我们不能进行 10 路合并 - 这将导致大量读取磁盘（读取每个元素，而不是块）。 合并的“顺序”的
    标准公式是（其中 M 是您的内存大小，并且是每个“缓冲区”（通常是磁盘块）的大小。kM/(2b)b
  3. 每个合并排序步骤都是通过b从先前迭代中生成的每个“运行”中读取条目来完成的 - 填充M/2内存。其余内存用于“预测”（允许以最少的 IO 等待进行连续工作）——从运行中请求更多元素，并用于输出缓冲区——以保证块中的顺序正确。
  4. log_k(N/(2M))使用这种方法的迭代总数k是运行次数（先前计算的），M是内存N的大小，是文件的大小。每次迭代需要对整个文件进行 1 次顺序读取和 1 次顺序写入。

也就是说 - file_size/memory_size 的比率通常远大于 10。如果您只对 10 的比率感兴趣，则可能会发生局部优化，但这不适用于更常见的情况file_size/memory_size >> 10

于 2012-12-08T08:48:44.937 回答