外部排序

一般讨论的排序都是内部排序,所谓外部和内部,是针对排序时的条件而言的,内部指所有的数据都可以直接拿到,而外部就是每次只能拿到一部分数据,最典型的现实场景

  • 对数组进行排序,整个数组当然都是在内存里的,可以直接拿到
  • 而对磁盘数据(比如文件)进行排序,要先把数据读进内存,而且限于内存的大小,内存中在某一时刻只能有一部分数据

外部排序的限制在于从磁盘读数据是一件很麻烦的事情,因为在磁盘上的数据存储并不是和在内存中那样是连续的,有个地址就可以直接访问,而是分散的,而且每次找一个数据都得寻道,旋转,再数据传输,排序的结果还得再写回磁盘,实际磁盘I/O的时间会远超在内存上操作的时间,所以要尽可能减少对磁盘的访问,I/O次数也成为外部排序时主要考虑的代价

这时候可以选什么排序算法来进行外部排序呢,很明显,选择排序,冒泡排序,这种每一趟都得把数据基本过一遍的算法是不行的,实际上可以想到,归并排序是个不错的选择

例如,一个有2000个记录的文件,每个磁盘块可以容纳125个记录,首先通过8次内部排序得到8个初始归并段R1到R8,每个段有250个记录,然后对该文件做两两归并,直至得到一个有序的文件

把内存分出三个缓冲区,两个输入一个输出,从R1和R2分别读一个磁盘块到输入缓冲区,归并到输出缓冲区,钥匙其中一个缓冲区空了就再读一个,然后把输出写到磁盘,再归并R3和R4,R5和R6,R7和R8,分别得到R1’-R4’

R1--R2      R3--R4      R5--R6      R7--R8
  |           |          |          |
  R1' ------- R2'         R3' ------- R4'
         |                       |
        R1'' ------------------ R2''
                    |
                    R

这样的话,一躺归并要读16个磁盘块,写16个磁盘块,内部排序也要读16次,写16次,总共的I/O次数:
$$
32\times 3 + 32=128
$$
如果改成四路归并,就只需要2趟归并:

R1--R2--R3--R4      R5--R6--R7--R8
       |                   |
      R1' --------------- R2'
                |
                R

这样外部排序的I/O次数就少了,但这样需要内存提供更多的缓冲区

败者树

增加归并排序的路数k固然可以减少I/O次数,但是内部归并的时间却增加了,因为在k个元素中选一个最小的需要做k-1次比较,每趟归并n个元素,要比较$(n-1)(k-1)$次,r个初始归并段,S趟归并总共需要的比较次数为:
$$
S(n-1)(k-1)=\log_k r(n-1)(k-1)=\frac{\log r}{\log k}(n-1)(k-1)
$$
可以看到随着k的增大,内部归并的时间也变多了,这时候就不能用普通的内部归并算法了

败者树主要用于选出k个元素里最小的那个,比如有8个元素,先两两比较,选出4强,再半决赛,在决赛,最后胜利的一定是冠军,但是只比了3次

               a
               |
      a ------------- e
      |               |
  a ----- c       e ----- g
  |       |       |       |
a---b   c---d   e---f   g---h

显然败者树是一颗完全二叉树,k路归并的话,从k个数据里选最小的,比较的次数为$\log k$,总的比较次数为
$$
S(n-1)\log k=(\log_k r)(n-1)\log k=(n-1)\log r
$$
这样内部归并比较的次数就与k无关了

但即使是这样,k也不是越大越好,k增大时,内存要提供更多个数的缓冲区,每个缓冲区的容量就会变小,内外存交换的次数会增加,因此当k过大时,归并趟数会减少,但外存I/O次数还是会增加

置换-选择排序

还有什么优化的方向呢,减少初始归并段的个数$r$也开始减少归并趟数S,内部排序在生成初始归并段的时候,依赖于内存工作区,只能生成相当于内存工作区大小的初始归并段,有什么操作可以跳出这个限制呢

基本思路是这样的

  1. 一个工作区,大小为w,先从文件读w个记录进去
  2. 从工作区里选一个最小的,输出并把值记录下来
  3. 往工作区里补一个记录,再找一个最小的但是比已经输出的值要大的,输出
  4. 重复,直到找不到比已经输出的值要大的
  5. 结束,一个初始归并段生成了

其中“从工作区里的w个记录里找一个最小的”的操作是基于败者树的

最佳归并树

置换-选择排序后,产生了一系列不等长的初始归并段,那么如何安排归并顺序呢,显然不同的顺序开销是不同的

比如,有9个初始归并段,长度为9,30,12,18,3,17,2,6,24

[9]-[30]-[12]   [18]-[3]-[17]   [2]-[6]-[24]
     |                |              |
    [51] ---------- [38] ---------- [32]
                      |
                    [121]

归并树的带权路径长度(WPL)为归并过程中的总读记录数,在上面的归并树中,WPL=242

实际上,可以用Huffman树的思想来优化归并树,将比较小的归并段先归并

     [2]-[3]-[6]
          |
     [9]-[11]-[12]  [17]-[18]-[24]
          |                |
[30]-----[32]------------[59]
          |
        [121]

这样的话,WPL只有223(把除了根节点的每个节点的值都加起来)

其实上图中的Huffman树是一颗严格的三叉树,即节点的度要么是0要么是3,但实际场景中这种刚刚好的场景是很少的,比如缺一个30,这时候构造Huffman时最后一次归并将是2路归并,WPL为193,但这并不是最优的

正确的做法应该是:补上1个值为0的节点

[0]-[2]-[3]
     |
    [5]-[6]-[9]             [12]-[17]-[18]
         |                        |
        [20]--------[24]---------[47]
                     |
                    [91]

那么如何确定应该补几个0节点呢?

  • 设度为0的节点有$n_0$个,度为k的节点有$n_k$个,如果是严格k叉树,有$n_0=(k-1)n_k+1$
  • 也就是$n_k=(n_0-1)/(k-1)$
    • 如果$k-1|n_0-1$,说明刚好
    • 如果$n_0-1\equiv u \mod k-1$,说明多出来$u$个,补上$k-1-u$个就好了

注意,初始节点全是度为0的节点

比如,8个初始节点,3路归并,$8-1\equiv1\mod 3-1$,多1个,补1个

总结

外部排序相较于内部排序,很重要的一点是考虑了实际环境的限制,而且外部排序的过程中也涉及到了内部排序

在外部排序的优化过程中,除去优化的方法,优化的思路更值得关注