为什么双向合并排序比单向合并排序更有效

Question

我正在维基百科上阅读关于外部排序的文章，我需要理解为什么两阶段合并比一阶段合并更有效。

Wiki：但是，单次合并有一个限制。随着区块数量的增加，我们将内存分成更多的缓冲区，因此每个缓冲区都较小，因此我们必须进行许多较小的读取，而不是较少的较大读取。

因此，对于100 MB内存中的50 GB的排序，使用单个合并过程是没有效率的：磁盘需要用500个数据块中的每个数据块（我们一次从每个数据块读取100MB/501~200KB）填充输入缓冲区，这占据了大部分排序时间。使用两个合并过程解决了这个问题。然后，排序过程可能如下所示：

Run the initial chunk-sorting pass as before.
Run a first merge pass combining 25 chunks at a time, resulting in 20 larger sorted chunks.
Run a second merge pass to merge the 20 larger sorted chunks.

谁能给我一个简单的例子来理解这个概念。我对在两阶段合并中分配更多的缓冲区感到特别困惑。




Answer 1

问题是随机访问开销，平均旋转延迟约为4毫秒，平均寻道时间约为9毫秒，平均访问时间约为10毫秒，而平均传输速率约为每秒150兆字节。因此，平均访问开销与读取或写入1.5兆字节所需的时间大致相同。

大型I/O减少了访问时间的相对开销。如果一次读取或写入10兆字节的数据，开销将减少到15%。使用wiki示例100MB的工作缓冲区和25个要合并的块，再加上一个写块，即3.8MB的块，在这种情况下，随机访问开销约为39%。

在大多数PC上，可以为1GB的工作缓冲区分配足够的内存，因此26个块，每个块超过40兆字节，将随机访问开销减少到3.75%。50块大约是每个块20兆字节，随机访问开销约为7.5%。

请注意，即使有50个块，它仍然是两遍排序，第一遍使用所有1gb缓冲区进行内存排序，然后写入排序的1gb块。第二遍合并所有50个块，从而产生html" target="_blank">排序文件。

50块的另一个问题是需要一个min堆类型的方法来维护排序信息，以确定哪个块的哪个元素是50个块中最小的，并被移动到输出缓冲区。一个元素移动到输出缓冲区后，一个新元素被移动到堆中，然后堆被重新堆化，这需要大约2个log2（50）操作，或大约12个操作。这比在进行50方式合并时进行49次比较以从一组50个元素中确定最小元素的简单方法要好。堆由结构、当前元素、这是哪个块（文件位置或文件）、块中剩余的元素数、...组成。