aLecture 15 | External Sorting

:material-circle-edit-outline: 约 1114 个字 :material-clock-time-two-outline: 预计阅读时间 4 分钟

内存里的数据只需要 \(O(1)\) 的时间来获取，但是在硬盘上就很麻烦了

当要排序的数据量远远大于我们的内存空间时，我们就得分治一下了，采用基于合并排序的外部排序

初始例子

下面我们用的是二路归并

我们假定我们外部的数据都存储在磁带 tape 上，而且我们有至少三个 tape 可以用

设内存可同时处理的 record 为 M=3

内存每次处理得到的结果序列为 run，也可以理解为内存一共处理了几次

然后我们交替地将run放入T2和T3，最后结果如下

接下来我们要 merge T2和T3，merge的方式就是从左往右依次比较T2和T3每个run的record，依次放入T1，得到结果如下

再来一次，结果如下

最后再来一次，就得到最终结果了

我们顺便给个新的概念 pass ，每个record从头到尾都读过一次了就是一个pass，像上面这次排序就有4个pass

准确来说，pass的数目有：

我们优化的思路是减少pass，一个措施是多路归并，一次处理三个run，比如下面的三路归并

就多一个tape，然后比较时是三个一起比

对于k路合并，我们一共需要2k个tape，因为从tape的角度来看，k路合并就是k个tape用于输入，k个tape用于输出，然后反复交换身份

接下来，我们想办法怎么减少tape的数目

我们可以让用于output的tape减少为1

回到二路归并，我们第一轮run完结果如下

然后开始归并，我们归并的结果都放入T1，然后又将T1的run 一部分 copy给T2，让T3用于output

我们这里是均匀归还，也可以自行设计归还几个runs，尽量减少需要copy 的 run 的数量

比如对于初始的34个run，如果我们第一次分为 13+21 就一次copy都不需要

满足斐波拉契数列的分法是不需要copy的，是最完美的，其它情况无论如何都得copy

对于k路，就是k阶的斐波拉契数列

总结一下，现在我们k路归并只需要k+1个tape了

实际上我们的内存也是得单独拿一个存放output的，因为不可能瞬间就将排好序的record从内存传输到硬盘

而且，上面我们假设一个block只有一个record，实际上一个block可以放很多record

所以实际情况是，tape上的两个block被输入给input buffers，并在这里对record进行排序，输出给output buffer，但是output buffer会小很多，所以会反复满，反复输出给tape

buffer往外写是I/O操作，此时排序就卡住了，因为output buffer被占用

我们可以再加一个output buffer，两个output buffer轮流工作，就能保证CPU并行进行排序和I/O不间断

同理，输入也可能导致CPU空闲情况，即一个input buffer空了的时候，又得通过I/O写进新的block，也是同理，我们可以给每个input tape多配一个input buffer

综上，对于k路合并，我们需要2k个input buffer和2个output buffer

减少pass的出发点就是这个公式，增大k：

但是无限加大k是不行的，input buffer会增加，但是总的内存不变，就导致每个buffer减小，导致I/O次数增加，传输时间增大

所以k是有一个最优解的，根据具体参数确定

我们的另一个思路是增长run以减少I/O次数

之前我们都是先固定run的长度再开始计算的，现在我们可以试试动态run：

不知道怎么简单地描述555，之后补吧

死空间，顺序最好，逆序最差

run需要反复归并，我们尝试用哈夫曼树找出最优解

归并的时间与被归并的record数量成正比

这里的操作次数可以看成 \(2+4 +6+5+11+15=43\)