外部归并排序的 I/O 分析

Question

我们有 9 个排序数组，每个数组大小 100 MB。我们的目标是在 RAM 大小为 100 MB 的机器上使用 9 路合并排序来合并它们，配置和步骤如下： • 90 MB 分配给输入缓冲区。 • 为输出缓冲区保留10 MB。 • 处理9路合并时： o 一旦输出缓冲区达到 10 MB 容量，将其内容传输到磁盘上的最终排序文件并清除输出缓冲区。 o 如果在合并期间输入缓冲区被清空，则用其关联的 100 MB 排序块中的下一个 10 MB 重新填充它。 • 继续该过程，直到合并所有块，从而生成完全排序的 900 MB 文件。 （计算此合并排序的总 I/O（以 MB 为单位）。）

我正在尝试 n 合并排序算法来解决这个问题，但没有答案， 我觉得我没理解这个问题 有人可以向我解释一下吗？

Answer 1

由于输入文件已经排序，该过程将一次合并 9 个文件，一次读取每个文件 10MB，一次写入合并文件也 10MB...所以使用的总 I/O 带宽为所有输入文件的总长度和输出文件的长度：读取 900MB，写入 900MB。

处理 I/O 非常简单：您可以使用

setvbuf

设置缓冲区大小，并将缓冲留给流处理函数。

编写最佳的 9 路合并更具挑战性。