每周学点大数据 | No.23 外排序（二）
No.23期
外排序（二）
Mr. 王：接下来我们用一个例子对磁盘归并排序进行说明。先来约定讨论的参数：N=24，M=8，B=2。
小可：嗯，一共有24 个数据项，内存能装下8 个数据项，一个磁盘块包含2 个数据项。
也就是说，内存可以装下4 个磁盘块。
我们就以1 ～ 24 这组数字为例吧。
其初始状态为：
24 1 23 19 20 5 18 16 4 7 8 9
10 15 17 14 3 2 6 11 12 13 22 21
首先，我们尽可能把内存装满。
24 1 23 19 20 5 18 16 4 7 8 9
10 15 17 14 3 2 6 11 12 13 22 21
每一条下画线代表一个磁盘块大小，用下画线表示它们被装进了内存。
然后，我们对已经放进内存中的这些值进行排序。
1 5 16 18 19 20 23 24
同理，我们也对放入内存中的下两路数字进行排序。
4 7 8 9 10 14 15 17
2 3 6 11 12 13 21 22
小可：现在已经保证了每一路内部是有序的，但是如何借助内存对它们进行归并呢？
Mr. 王：内存只能容下4 个磁盘块，三路刚好保证每一路可以拿出一个磁盘块放入内存中，剩下的一块我们用来做I/O 的缓冲区。接下来，我们将每一路的首块放入磁盘中。
1 5
4 7
2 3
[] []
对这几个值进行归并。
较小的1 和2 先被放入缓冲区里，同时清空它们在内存中的位置。
[] 5
4 7
[] 3
1 2
此时缓冲区满，将其写回到磁盘里，然后清空缓冲区。
[] 5
4 7
[] 3
[] []
接下来，我们将较小的3 放入缓冲区中。此时，来自第三路的磁盘块被彻底清空，所以我们从外面调入一个来自第三路的磁盘块。
[] 5
4 7
[] []
3 []
[] 5
4 7
6 11
3 []
接下来，我们将4 放入缓冲区中，缓冲区满，写回外存。
依此类推，不断地执行这个过程，就可以最终实现外排序了。
小可：那这个外排序算法的I/O 复杂性又如何呢？
Mr. 王：好，接下来我们就以M、N、B 三个值为参数，对其I/O 复杂性进行推导。首先考虑：对整个数据集合进行一次浏览或者说扫描需要多少次I/O ？将内存用数据填满又需要多少次I/O ？
小可：扫描对于磁盘而言是I/O 线性的，所以是N/B。将内存填满的I/O 次数，也就是内存可以容纳的磁盘块数目，应该是M/B。
Mr. 王：回想一下，在第一轮归并排序中，我们都做了什么？进行了多少次IO ？
小可：第一轮，我们把一部分磁盘块装入内存，在内存中排序，然后再把一部分装入内存，在内存中排序……不断地执行，直到所有的数据都进入一次内存！
Mr. 王：所以呢？
小可：相当于对数据执行了一次扫描，所以应该是N/B 次I/O ！
Mr. 王：很好。那么再想一想，在第二轮的执行过程中，又进行了多少次I/O 呢？
小可：第二轮，开始执行归并时，我们每一次都将每一路的一个磁盘块放进磁盘中，在不断的归并过程中，其实也是每一个磁盘块都放进一次内存，所以也是N/B 次I/O。
Mr. 王：这意味着每一轮都会执行(N )B_ 次I/O。加上一个q，是因为我们前面的计算只把输入内存考虑在内了，并没有计算每轮一次的缓冲区满输出到内存，所以使用 ( ) NB_ 这个描述要更加准确一些。
小可：可是我们只知道每一轮的情况，要求解复杂度的问题，还需要知道一共执行了多少轮次。
Mr. 王：很好，我们先来思考这样一个问题：每一轮的排序，使得已经有序的数组变得多大？第一轮是一个特殊的例子，我们让每一路内部实现了有序。每一个内部有序的组均有M/B个磁盘块。那么接下来的每一次，内存中都有M/B-1 个磁盘块作为每一路的头。
小可：多出的那一个是缓冲区？
Mr. 王：对。此外，每一个头都带有一个含有M/B 个磁盘块的有序的路，这样就实现了对
个元素的排序。第三次，我们用同样的方法，完成了
个元素的排序。
小可：那么究竟归并到什么时候算法可以结束呢？
Mr. 王：假设经过k 轮之后，算法停止，可以列一个方程：
小可：除了第一轮，我们都完成了
路的归并。只要整个归并的数据规模达到了N/B，就成功地归并了所有的元素。
Mr. 王拿出一张纸，说：来吧，发挥你数学基础的作用，解一下K。
小可对Mr. 王竖起了大拇指，说 ：解得不错，我们简化一下这个结果，就是
综合每一次的I/O 复杂性和总次数，就可以求得整个算法的复杂度为
这个结果看起来依然比较复杂，该事实上，该式子可以简化
，因为
加之此项在log 内，是一个低阶项，在计算复杂度时可以直接忽略它。
Mr. 王：其实和内存算法中的快速排序类似，还有一个外排序版本的快速排序。就基本思想而言，和内排序一样。首先选出一个分界点，通过算法操作使得数组中左边的数都比它小，右边的数都比它大，然后对左边、右边分别执行这个步骤，不断地递归执行下去，就可以实现整个数组的排序了。
小可：哦，那么它的外排序版本又是怎么做的呢？
Mr. 王：快速排序的最重要动作就是划分。只是由于外存的原因，划分要更加有技巧，划分的终点，就是当每一块都可以被放进内存时。
还是用上面的例子来解释这个算法吧。
24 1 23 19 20 5 18 16 4 7 8 9
10 15 17 14 3 2 6 11 12 13 22 21
首先，在输入缓冲区中读入第一个磁盘块24 1。
然后，为后面的3 个磁盘块设置两个分界点。为了划分均匀，我们选用8 和16，至于如何选出8 和16 的后面再讲解。
现在内存中是24 1,[][],[][],[][]。后面的3 个磁盘块的两个分界点为8 和16。此时输入缓冲区里的数值是24 和1，我们分别将它们放进大于16 和小于8 的两个部分中，内存中变为：
[][],1[],[][],24[]
缓冲区已经空了，我们再将23 和19 放进来，23 大于16，内存中换为：
[]19,1[],[][],24 23
此时我们发现19 也大于16，但大于16 的块已经写满了，为24 23，所以将24 和23 写回磁盘中，将它们在内存中占据的位置空出来：
[]19,1[],[][],[][]
再将19 放进来：
[][],1[],[][],19[]
之后将20 和5 放进内存：
20 5,1[],[][],19[]
接下来是：
[][],1 5,[][],19 20
将1 5,19 20 分别写到外存中。
……
不断执行上面的步骤，最终：
第一组 1 5 4 7 8 3 2 6
第二组 16 9 10 15 14 11 12 13
第三组 24 23 19 29 18 17 22 21
虽然组分好了，而且组间是有序的，但是每一组内部依然是乱序的状态，所以要继续对它们进行排序。
小可看了看写在纸上的数据，说：现在每一组都已经能够放入内存中了。所以对每一块用内存排序，就可以实现对整个数组的排序了。
Mr. 王：问个问题：假如执行过第一轮快排以后，划分的组仍然不能装入内存中，怎么办呢？
小可：只要对每一部分再执行一轮外排序就好了。如果还是不行，就再执行一轮。
Mr. 王：很好，这就是递归的体现。现在又到了分析复杂度的时候了，还是以M、N、B 为参数。
先来考虑：每一轮快速排序，I/O 复杂度是多少？
小可：这个好像比较复杂啊。
Mr. 王：想想看，虽然每个数据在内存中被拿来拿去，但是不论如何，它只是从缓冲区进来，直到该磁盘块被填满才离开内存。而离开的不会在本轮中再进来。
小可：我明白了，在每一轮中，每个数据都会进入到内存中一次，同时也都会离开内存一次，这说明I/O 次数应该是一个N/B 的同阶函数
。
.
Mr. 王：嗯，那我们一共要进行多少轮呢？第一次划分，我们将数据分成了
组，这是因为内存中有M/B个磁盘块，留下一个作为缓冲区，那么每一组中有
个磁块，在第二次划分中，我们将每一组
个磁盘块再划分为
组，每一组就有
个元素。还记得要划分到什么时候为止吗？接下来的推导由你来完成吧。
小可：划分要持续到每一组都可以装入内存中为止，这意味着经过k 轮的划分，应该达到
的效果。把k 解出来，就是
。根据前面的内容进行处理，可以求得整个算法的复杂度为
，事实上，该式子可以简化为
这种形式和归并排序是一样的啊。
Mr. 王笑着说：哈哈，学得真快，非常好。
内容来源：灯塔大数据