2

如果我有一个非常大的列表存储在需要排序的外部存储器中。假设这个列表对于内存来说太大了，那么在设计外部排序算法时应该考虑哪些主要因素？

4

1 回答 1

3

在构建自己的外部排序之前，您可能会查看操作系统提供的工具。Windows 有 SORT.EXE，它在某些文本文件上运行良好，尽管它有……特性。GNU 排序也运行良好。您可以尝试其中任何一个数据子集，看看它们是否会满足您的需求。

否则 。. .

外部排序是一种非常有名的算法。总体思路：

  1. 将尽可能多的数据加载到内存中。
  2. 对该块进行排序。
  3. 将该块写入外部存储器。
  4. 重复步骤 1-3，直到所有块都已排序和存储。
  5. 合并已排序的块。

假设您有每个n项目被分成元素k块m（so n = k*m），第一部分（步骤 1-4）花费的时间与 k*(m log m) 成正比。

完成步骤 1-4 后，您已对项目块（或可能是项目块，以及一个项目较少的一个块）k进行了排序。或者，如果您正在对字符串进行排序，您的块大小大致相同，但每个块中的字符串数量会有所不同。mk-1mk

您现在需要合并这些已排序的块。执行此操作的典型方法是使用k-way merge。

您创建一个包含每个块的第一项的最小堆。然后从堆中选择根项，它是所有块中最小的项。您将其作为第一项输出。然后，从最小的块中读取下一项，并将其放在堆上。那是：

create heap
for each block
    read item and add to heap
end for

while heap is not empty
    remove smallest item from heap
    write to output
    read next item from block that contained smallest item
    add to heap
end while

这部分算法是O(n log k)，其中n是项目的总数，k是块的数量。

正如其他人所指出的，有效的外部排序的一个关键是减少 I/O。外部存储很慢。我上面描述的算法做尽可能少的 I/O。每个项目从外部存储读取两次，每个项目写入外部存储两次。其他乍一看更简单或更快的算法在处理真实数据时最终会慢得多，因为它们在 I/O 上花费了太多时间。

如果您对实现感兴趣，我在一段时间前写了一系列关于对非常大的文本文件进行排序的文章。代码是 C#，但描述应该允许您轻松翻译成任何语言。

于 2016-07-21T14:42:06.797 回答