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

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

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

简单算法

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

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

示例:

初始状态:

第1,第2步之后:

第3,第4步之后:

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

完成!

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

多路合并

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

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

多相合并

在上面的多路合并中,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阶斐波那契数列:

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的过程。

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

04-25 02:42