jlearning.cn

《数据结构与算法设计》读书笔记——外部排序

上个月在某养猪场面试,面试官问了一个问题:“如何用256M内存的机器对一个2G的数据进行排序”。之前没看过这方面的内容,想了一下说用归并排序,然后简略的说了一下我的想法。现在再来看书里关于外部排序的内容,只能说当时的大方向没错,但是剩下的具体实现、外部空间复杂度计算、时间复杂度计算和优化等都没考虑到位。

因为计算机的外部访问是非常慢的(相对比从内存读数据),如果使用和“把数据全部读入内存然后排序”相同的算法,再加上外部存储例如磁带是只能顺序访问,那么任何算法都需要$\Omega(N^2)$次外部数据访问,将是非常可怕的耗时。所以需要有专门用于外部排序的算法。

下面首先第一部分介绍基于归并排序的简单算法,然后第二部分在简单算法的基础上让其支持多路归并可以提高效率,第三部分首先在简单算法上应用多相合并,可以节约外部存储的空间,然后扩展到多路归并上,第四部分针对用于归并的顺串进行改造,在特定的情况下可以提高算法效率。

简单算法

使用归并排序的思想,简单的双路归并需要四盘磁带(就是外部存储)。最初的数据在$T_{a1}$上,内存为M,就是每次可以使用排序算法对M个数据进行排序。

  1. 依次从$T_{a1}$上读入M数据,进行排序。
  2. 然后交替的输出到Tb1和Tb2上。每组排过序的记录叫做一个顺串
  3. 将 Tb1和Tb2的第一个顺串取出来将两者合并(过程参考归并算法),将结果输出到$T_{a1}$上。
  4. 继续上一个步骤,交替的输出到Ta1和Ta2上。直到Tb1或Tb2为空。如果剩下一个顺串,拷贝到适当的磁带上。
  5. 这样我们在Ta1和Ta2上得到长度为M的顺串,重复上面的过程,知道得到长度为N的顺串。

示例:

初始状态:

$T_{a1}$ 81 94 11 96 12 35 17 99 28 58 41 75 15
$T_{a2}$
$T_{b1}$
$T_{b2}$

第1,第2步之后:

$T_{a1}$
$T_{a2}$
$T_{b1}$ 11 81 94 17 28 99 15
$T_{b2}$ 12 35 96 41 58 75

第3,第4步之后:

$T_{a1}$ 11 12 35 81 94 96 15
$T_{a2}$ 17 28 41 58 75 99
$T_{b1}$
$T_{b2}$

重复这个从Ta1 Ta2归并到Tb1 Tb2,从Tb1 Tb2归并到Ta1 Ta2的过程:

$T_{a1}$
$T_{a2}$
$T_{b1}$ 11 12 17 28 35 51 58 75 81 94 96 99
$T_{b2}$ 15
$T_{a1}$ 11 12 15 17 28 35 51 58 75 81 94 96 99
$T_{a2}$
$T_{b1}$
$T_{b2}$

完成!

我们“从Ta1 Ta2归并到Tb1 Tb2,从Tb1 Tb2归并到Ta1 Ta2”这个过程用了3趟。因为第一次顺串的长度为M,在二路归并的情况下,每次将顺串的长度延长一倍,需要$\lceil log_2(N/M)\rceil$趟。

多路合并

上面的简单算法就是二路合并,我们将其扩展到一般状态——k路合并。

k路合并需要2k盘磁带,每次将顺串的长度扩充为原来的k倍。在合并的时候,在k个元素中发现最小值是比二路合并复杂的地方,可以使用优先队列。多路合并和二路合并区别不大,就不举例子了。k路合并需要的趟数是$\lceil log_k(N/M)\rceil$

多相合并

在上面的多路合并中,k-路合并需要2k盘磁带。使用多相合并后,只使用2k-1盘磁带也可以达到相同的效果,可以节省外部存储空间。下面看如何用三盘磁带完成2-路合并:

  1. $T_1$上有34个顺串长度的数据,可以选择排序后在$T_2$$T_3$上分别输出17个顺串。
  2. 合并输出到$T _1$上,$T_1$上有17个顺串。
  3. 将8个顺串从$T_1$拷贝到$T_2$上,然后合并到$T_3$上,这时候$T_3$有9个顺串。
  4. 每次拷贝二分之一个顺串到一个空的磁带上,然后合并到剩下的那个空的磁带上。

可以优化一下,让每次合并完成之后天然形成两个磁带有顺串,一个为空的情景:

  1. 把$T_1$上的数据排序后,把21个顺串放到$T_2$上面,13个放到$T_3$上。
  2. 合并之后,$T_3$为空,$T_1$上有13个顺串,$T_2$上有8个顺串。
  3. 合并,$T_2$空,$T_3$上有8个顺串,$T_1$上有5个。重复这个过程。

第一步分配的策略是:如果总顺串的数量是斐波那契数$F_N$,那么将顺串分解成F(N-1)和 F(N-2)。如果不是斐波那契数,需要用一些哑顺串(dummy run)来填补磁带。

将上面三盘磁带完成2-路合并扩展到k-路的多相合并,顺串分解使用k阶斐波那契数列:

$$F^{(k)}(N)=F^{(k)}(N-1)+F^{(k)}(N-2)+……+F^{(k)}(N-k)$$

$$F^{(k)}(N)=0,0\le k-2$$

$$F^{(k)}(k-1)=1$$

5阶斐波那契数列就是:

0,0,0,0,1,1,2,4,8,16,31,61……

替换选择

上面的排序算法中,第一步顺串的生成都使用了常规内存排序的方法,每次可以生成和内存容量一样大的有序数列。在替换选择算法中,无序数列平均可以生成2M长度的顺串。

  1. M个数据被读入内存,并放到一个优先队列中。执行一次DeleteMin把最小记录输出到磁带上。
  2. 内存空出一个位置,在从磁带读入下一个记录,如果比刚刚输出的数据要大,放入优先队列。否则把这个新元素存入优先队列的死区(dead space)。
  3. 重复上一个步骤,知道优先队列的大小为0,结束第一个顺串的构造。
  4. 使用死区中的所有元素建立一个新的优先队列,重复1,2,3的过程。

替换选择在一些情况下,如果说大部分的数都是逆序的,效果并不比表标准算法好。但是,如果输入数据是大致顺序的,那么可以第一步就产生很长的顺串,减少来回归并的趟数。