题6

题6

题目

Q:在做 路平衡归并排序的过程中，为实现输入/内部归并/输出的并行处理，需要设置 ( ①) 个输入缓冲区和 ( ② ) 个输出缓冲区.
①
A. 2
B.
C.
D.
②
A. 2
B.
C.
D.

分析

A:主题题目里面的并行处理这个描述和要求
“平衡归并” 中的 “平衡” 主要体现在两个方面：

1. 归并路数的平衡:
   在外部排序中，我们通常使用多路归并来提高效率。 “k 路归并” 指的是每次合并 k 个有序段。 “平衡” 意味着我们尽量保持每次归并的路数 k 相同， 这样可以保证归并树的形态相对平衡，从而减少总的归并趟数。
2. 归并段大小的平衡:
   理想情况下，我们希望每次参与归并的各个段大小尽可能相近。 这是因为，如果某些段很大，而另一些段很小， 那么就会导致归并操作的不平衡， 大段会参与更多次的比较，影响效率。
   为了实现归并段大小的平衡，通常会用到一些技巧，例如：

• 置换-选择排序: 用于生成初始归并段时，可以尽量使各个段的长度均衡。
• 添加虚段: 如果初始归并段的数量不能构成严格的 k 叉树，可以添加一些长度为 0 的 “虚段” 来使其平衡。
  总的来说，“平衡归并” 中的 “平衡” 是指尽力保持归并过程的均衡，无论是归并路数还是归并段大小， 其最终目标都是为了减少外存读/写次数，提高外部排序的效率。

解

D、A
相比普通的 路归并: 需增加一个输出缓冲区,当一个输出缓冲区满时,输出一个缓冲区的同时归并程序可向另一个输出缓冲区填充数据,这就实现了内部归并和输出的并行。
需增加 个输入缓冲区,当 个输入缓冲区正在运行时,外部可向新增的 个缓冲区写入数据,这就实现了输入和内部归并的并行。
综上,需设置 2 个输出缓冲区, 个输入缓冲区。