提问人：lol j2 提问时间：10/26/2023 更新时间：11/22/2023 访问量：42
外部合并排序的 I/O 分析
I/O Analysis for External Merge Sort
问：
我们得到了 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 合并排序算法来解决这个问题，但没有答案， 我觉得我不明白这个问题 有人可以向我解释一下吗？
答：
0赞
chqrlie
11/22/2023
#1
由于输入文件已经排序，因此该过程将一次性合并 9 个文件，一次读取每个文件 10MB，一次写入合并后的文件 10MB......因此，使用的总 I/O 带宽是所有输入文件的总长度和输出文件的长度：读取 900MB，写入 900MB。
处理 I/O 非常简单：您可以使用流处理函数设置缓冲区大小，并将缓冲留给流处理功能。setvbuf
编写最佳的 9 路合并更具挑战性。
评论