外部排序（外排,external sort）

Question

关于外部排序，求问一下这三道题

不需要先把records拿到内存进行排序吗

关于外排的并行算法

Answer 1

引自免费微信小程序：皆我百晓生

图1解答

给定1亿条记录，每条记录大小为256字节，内存大小为128MB。使用简单的两路合并方法，我们需要进行多少次遍历？

首先，计算内存可以容纳的记录数量。内存大小为128MB = 128 * 1024 * 1024字节。每条记录大小为256字节。

[ \text{内存可容纳记录数} = \frac{128 * 1024 * 1024}{256} = 524288 ]

这意味着每次遍历时，我们可以处理大约524288条记录。对于1亿条记录，我们首先将这些记录分成多个块，每个块的大小不超过内存容量。

由于1亿远大于524288，我们将数据分批读入内存进行排序，然后输出到磁盘，形成多个排序好的块（runs）。接下来，通过两路合并这些块，直到所有数据都被排序为止。

设初始有N个块，每轮两两合并后，块的数量减半。因此，合并次数为log2(N)。但这里的N不是块的实际数量，而是由总记录数除以单次可处理记录数得到的理论上的块数。这里我们计算N：

[ N = \frac{100000000}{524288} ≈ 190.7 ]

由于N不是2的整数幂，我们取最接近的2的幂，即N ≈ 128。因此，合并次数为：

[ \log_2(128) = 7 ]

答案: D.7

图2解答

在外部排序中，假设有长度分别为2、8、9、5和3的5个run。下列哪种合并顺序可以获得最少的合并时间？

这个问题实际上是在询问哪种合并策略最高效。在外部排序中，合并效率通常与合并树的形状有关，理想情况下，我们希望创建一个平衡的二叉树，这样每次合并的开销都是最小的。

选项C和D看起来更合理，因为它们试图保持合并树的平衡。然而，C选项最终将长度为9的run与其他合并后的run合并，这可能导致最后一次合并的时间较长。D选项在每次合并中都尽量保持合并run的长度接近，这是更有效的策略。

答案: D. merge runs of lengths 2 and 3 to obtain Run#1; merge runs of lengths 5 and 8 to obtain Run#2; merge Run#2 with the one of length 9 to obtain Run#3; merge Run#1 and Run#3

图3解答

假设内部内存可以同时处理12个数字，并且有以下两个磁带上的run： Run 1:1,3,5,7,8,9,10,12 Run 2:2,4,6,15,20,25,30,32 使用两路合并，4个输入缓冲区和2个输出缓冲区进行并行操作。下列哪些操作没有并行执行？

在这个问题中，我们有4个输入缓冲区和2个输出缓冲区。在两路合并过程中，我们需要从两个输入流中读取元素，将其比较并写入输出流。由于我们有4个输入缓冲区，意味着我们可以同时处理两个独立的读取操作。

选项A、B和C描述了正常情况下的并行操作。然而，在选项D中，“9和15被合并到输出缓冲区”表明这两个值正在同一输出缓冲区中被写入，但是“10和12被读入输入缓冲区”则表明新的读取操作已经开始，而前一个输出操作可能还没有完成。这可能意味着读取和写入操作没有完全并行。

答案: D. 7和8被写入第三磁带；9和15被合并到输出缓冲区；10和12被读入输入缓冲区

以上分析基于外部排序的基本原则和并行操作的效率考虑。