外部合并排序算法

Question

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

外部排序的一个例子是外部合并排序算法，该算法将每个块都放入内存中进行排序，然后将已排序的块合并在一起。例如，为了仅使用100 MB的RAM对900兆字节的数据进行排序: 1)在主存中读取100 MB的数据，并通过一些常规方法进行排序，比如快速排序。2)将已排序的数据写入磁盘。3)重复步骤1和步骤2，直到所有数据都被排序为100 MB块(有900 MB/100 MB=9块)，现在需要合并到一个输出文件中。4)将每个排序块的前10 MB (= 100 MB / (9块+ 1))读入主内存中的输入缓冲区，并为输出缓冲区分配剩余的10 MB。(在实践中，它可能提供更好的性能，使输出缓冲区更大，而输入缓冲区稍微小一些。) 5)执行9路合并并将结果存储在输出缓冲区中。如果输出缓冲区已满，则将其写入最终排序文件，并将其清空。如果9个输入缓冲区中的任何一个变为空，则使用其关联的100 MB排序块的下一个10 MB填充，直到没有来自该块的更多数据可用为止。

我无法理解第四步here.Why读取前10 MB内存时，我们有100 MB的可用memory.How来决定外部合并中的通过次数?我们会对每个块进行排序并将它们存储在9个文件中吗？

Answer 1

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

要进行k-way合并，可以存储k个读取指针，每个文件一个，并反复查看所有k元素，取最小值，然后将该元素写入输出流，并提前相应的读取指针。

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

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

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

这一方法将正确工作，但它将是痛苦的缓慢。请记住，磁盘I/O操作比主存中相应的操作花费的时间要长得多。这个合并算法最终会执行Θ(n)磁盘读取(我假设k比n小得多)，因为每次选择下一个元素时，我们都需要进行另一次读取。这将是令人望而却步的，所以我们需要一个更好的方法。

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

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

我们可以采取类似的方法来最小化写入。我们不是一次只写一个元素到磁盘(需要Θ(n)写)，而是存储一个W大小的缓冲区，在执行过程中将元素积累到其中，并且只在缓冲区填满后才编写。这需要Θ(n / W)磁盘写入。

显然，使R和W更大将使这一方法更快，但代价是更多的内存。具体来说，我们需要kR项存储大小为R的读取缓冲区的k个副本的空间，而W项需要空间来存储大小为W的写入缓冲区，因此，我们需要选择R和W，以便kR +W项适合主存。

在上面给出的示例中，您有100 to的主存和900 to的排序。如果将数组拆分为9块，则需要选择R和W，以便(kR + W)·sizeof(record)≤100·。如果每个项目都是一个字节，那么选择R=10 is和W=10 is确保一切都适合。这也可能是一个很好的发行版，因为它保持了较低的读写次数。