外部合并排序算法

Question

我在理解外部排序算法中的合并步骤时遇到了一定的困难。我在维基百科上看到了这个例子，但我无法理解。

外部排序的一个例子是外部合并排序算法，它对每个适合RAM的块进行排序，然后将排序后的块合并在一起。例如，对于仅使用100 MB RAM对900 MB数据进行排序：1）读取主内存中的100 MB数据，并通过一些常规方法进行排序，如快速排序。2） 将排序后的数据写入磁盘。3） 重复第1步和第2步，直到所有数据都是经过排序的100MB块（有900MB/100MB=9个块），现在需要将这些块合并到一个单独的输出文件中。4） 将每个已排序块的前10MB（=100MB/（9个块1））读入主内存中的输入缓冲区，并将剩余的10MB分配给输出缓冲区。（实际上，它可以提供更好的性能，使输出缓冲区更大，而输入缓冲区稍小。）5） 执行9路合并并将结果存储在输出缓冲区中。如果输出缓冲区已满，将其写入最终排序的文件，然后清空。如果9个输入缓冲区中的任何一个为空，则用其关联的100 MB排序块中的下一个10 MB填充它，直到该块中没有更多可用数据。

我无法理解这里的第四步。当我们有100MB的可用内存时，为什么要读取前10MB的内存。如何确定外部合并中的通过次数？我们会对每个区块进行排序并将其存储在9个文件中吗？

Answer 1

假设您将要排序的范围拆分为k个排序的元素块。如果您可以对这些已排序的块执行k-way合并，并将结果写回磁盘，那么您就已经对输入进行了排序。

要进行k路合并，您存储k个读取指针，每个文件一个，并重复查看所有k个元素，取最小的，然后将该元素写入输出流并推进相应的读取指针。

现在，由于所有数据都存储在磁盘上的文件中，所以实际上无法存储指向尚未读取的元素的指针，因为无法将所有内容都放入主内存中。

让我们从一个简单的方法开始，来模拟正常的合并算法会做什么。假设您在内存中存储了k个元素的数组。将每个文件中的一个元素读入每个数组插槽。然后，重复以下步骤：

• 扫描阵列插槽，取最小的
• 将该元素写入输出流
• 通过从相应的文件中读取下一个值来替换该数组元素

这种方法可以正常工作，但速度会非常慢。请记住，磁盘I/O操作比主存储器中的相应操作花费的时间要长得多。这种合并算法最终会执行θ（n）磁盘读取（我假设k比n小得多），因为每次选择下一个元素时，我们都需要进行另一次读取。这将非常昂贵，因此我们需要更好的方法。

让我们考虑修改一下。现在，我们不再存储一个k个元素的数组，每个文件一个，而是存储一个k个插槽的数组，每个插槽保存相应文件中的前R个元素。为了找到下一个要输出的元素，我们扫描整个数组，对于每个数组，查看我们尚未考虑的第一个元素。我们取最小值，将其写入输出，然后从数组中删除该元素。如果这清空了数组中的一个插槽，我们可以通过从文件中读取更多元素来补充它。

这更复杂，但它大大减少了我们需要进行的磁盘读取。具体来说，由于元素是以大小为R的块读取的，所以我们只需要进行Θ（n/R）磁盘读取。

我们可以采取类似的方法来最小化写操作。我们存储一个大小为W的缓冲区，在运行时将元素累积到其中，并且只在缓冲区填满时写入，而不是一次将每个元素写入磁盘（需要Θ（n）次写入）。这需要Θ（n/W）磁盘写入。

显然，将R和W变大将使这种方法运行得更快，但这是以牺牲更多内存为代价的。具体来说，我们需要空间让kR项存储大小为R的读缓冲区的k个副本，并且我们需要空间让W项存储大小为W的写缓冲区。因此，我们需要选择R和W，以便kR W项适合主内存。

在上面给出的示例中，您有100MB的主存储器和900MB要排序。如果您将数组分成9个部分，那么您需要选择R和W，以便（kR W）·sizeof（记录）≤100MB。如果每个项目都是一个字节，那么选择R=10MB和W=10MB可以确保一切都合适。这可能也是一个非常好的分布，因为它保持了较低的读写次数。