编程珠玑之外排序

编程珠玑之外排序(External Sorting)

外排序,主要应用于对海量数据的排序处理,当数据量特别大以至无法一次性将其装入内存中时,我们常用的快速排序,并归排序,堆排序等排序算法是无法使用的,这也是将这些常用排序算法称之为内排序算法的原因,无法一次性全部装入内存的海量数据被放置在磁盘上(文中我们将放在磁盘上的海量数据称之为大文件),如何高效的排序磁盘上的数据就是外排序算法设计时要考虑的首要问题,毕竟磁盘的访问速度跟内存相比差好几个数量级(磁盘的访问速度是毫秒级的,内存的访问速度是纳秒级的),所以外排序算法设计的关键还是如何高效的利用现有的内存空间,在实际应用中外排序算法的性能(不考虑额外的磁盘I/O情况下)可以达到O(nlgn)

编程珠玑中的外排序问题

输入:

输入一个文件,该文件含有不重复且小于n的自然数,至多n个,这里n=107

输出:

一个包含已排序(递增)输入数据的文件

注:

本文对外排序算法的介绍将会围绕编程珠玑中给出的外排序问题(即上面的例子),该例仅仅只是作为讲解之用,外排序在实际应用中要比示例更为复杂,比如排序的内容也许不是数字,而且内容量级远远高于示例,同样本例中数据内容不可重复这一限制在实际应用中并不一定要有,珠玑中之所以这样规定是为了引入**位图向量**这一知识点(后面会有介绍的)

外排序算法的种类

理论上只要可以对大文件进行排序的算法都可以称其为外排序算法,但由于某些算法频繁的I/O或者依赖于特定的数据集,并不通用,例如编程珠玑中给出的多通过算法(multi-pass),该算法通过多次遍历大文件来排序数据,每次遍历时都从文件中提取特定区间的数据通过内排序后写入到输出文件中,假设大文件中的数据取值范围是0~100,第一次遍历文件时从中提取0~10范围的数据,内排序提取出的数据后写入输出文件,第二次遍历文件时从中提取11~20范围的数据,内排序后写入输出文件,如此共遍历10次排序完成,此算法是十分低效的,大文件中的每个数据将被读取多次(准确来讲读取次数等于取值区间数目),此外编程珠玑中还提到了使用位图向量实现的排序算法(后文会有介绍),准确来讲位图向量仅仅只是一种数据结构而已(你可以在任何适当的场景中使用它,并不仅限于外排序),所以它并不是通用的外排序算法,在实际应用中提到的外排序往往是指外归并排序,因为该外排序算法具有优良的性能以及宽泛的通用性,后文中提到的外排序一般都指外归并排序,有特别的说明除外

外排序的步骤

归并排序利用了分而治之的思想,将待排序的大文件分为若干数据块分别对其排序,再将排序后的各数据块合并起来,正是因为归并排序可以逐块处理数据,使得不必一次性将整个数据集载入内存(而只是排序特定的数据块),这就是归并排序算法可以用于外排序的原因,外排序的主要步骤:

1. 分,将大文件从逻辑上划分为若干数据块,一般来说数据块是均等划分的,划分的大小由可用内存大小决定

2. 治,使用内排序算法(快速排序,堆排序等)分别对各个数据块进行排序,并将结果写入到中间文件中

3. 并,从上步生成的中间文件中读取数据进行合并,并将结果写入到输出文件中

上面仅仅只是外排序的大致算法框架,在具体实现过程中还有许多细节需要完善,并利用某些方法来优化性能

外排序流程图

                     磁盘                            内存(容量为M)                 结果

    阶段一:    ----------------

              |     数据块0    |                  -----------------            中间文件file-0

              -----------------                  |               |           --------------

              |     数据块1    |                  | 使用高效的内排序 |           | 已排序数据块0 |

              -----------------                  | 算法排序数据块i,|           --------------

              |     ......    |                  | 并将其输出到中间 |               ......

              -----------------     读入数据块i    | 文件file-i中   |            

              |     数据块i    |    ----------->  |               |            中间文件file-n

              -----------------                  |               |           --------------

              |     ......    |                  -----------------           | 已排序数据块n |

              -----------------                                              --------------

              |     数据块n    |

              -----------------

    阶段二:       中间文件file-0

               -----------------

               | 段0 | 段1 | 段m |

               -----------------                ---------------------

                      ...                       | 段a \              |

                  中间文件file-i                 | 段b  \       -----  |             最终输出文件中

               -----------------    从文件读入段  | 段c  |  多   | 输 | |  缓存区输出     含有排序好

               | 段0 | 段1 | 段m |  -----------> | 段d  \  路 \ | 出 | | ---------->     的数据

               -----------------                | 段e  /  归 / | 缓 | |

                      ...                       | 段f  |  并   | 存 | |

                  中间文件file-n                  | 段g /       -----  |

               ------------------               | 段h /              |

               | 段0 | 段1 | 段m |               ---------------------

               ------------------

优化外排序以及详解流程图

外排序算法优化的主要工作是尽量减少磁盘I/O次数,上图中外排序流程图跟外排序算法框架相比多了很多内容,有些内容并不是完成排序的必要步骤,而仅仅是为了优化外排序算法,比如在阶段二,以数据段为单位读入中间文件可以少对中间文件的读取次数,多路归并的输出结果先写入缓存中再写入输出文件可以减少对输出文件的写入次数,那么究竟应该从哪些方面入手对外排序算法进行优化呢?

  1. 在阶段一,一次内排序的内容尽可能的多些。如果我们使用常规的内排序算法,显然每次内排序处理的内容由可用内存容量M决定,但我们可以使用改进版的置换堆排序算法,该算法同堆排序一样在初始时将M大小数据载入构建最小堆,关键在于弹出堆顶数据后,对大文件待读入数据进行测试,若待读数据大于刚刚弹出的堆顶数据,则将待读数据插入堆中,否则继续弹出堆顶并同待读数据比较,直到堆为空,该算法的核心思想是如果待读数据大于已排序数据中最大的那个,显然将待读数据添加到堆不会影响数据递增的排序规则,该算法最糟糕情况下可以一次处理M大小数据量,平均情况是2M数据量,最好情况是一次性处理整个大文件(如果大文件是已排序好的)

  2. 在阶段一中是否应该使用输入/输出缓存区。如果使用常规的内排序算法,一次性读入待排序数据块,一次性写出已排序数据块显然是不需要通过使用缓存区来减少I/O的,但是如果使用的是置换堆排序算法呢?该算法将数据逐个弹出,如果没有输出缓存区就意味着每弹出一个数据写入一次中间文件,这样频繁的I/O完全抵消了该算法带来的好处(甚至低于常规内排序的性能),同时由于该算法不断测试大文件的待读数据,这样的测试应该避免I/O的访问,所以如果使用了置换堆排序算法则一定要从可用内存空间中规划出输入/输出缓存区,至于缓存区的大小则需要根据实际情况进行调优,如何在堆大小和缓存区大小之间找到一个平衡点是个实战问题

  3. 在阶段二,输入/输出缓存区的使用。毫无疑问输入缓存区是必要的,以段为单位将中间文件的数据载入可以减少对中间文件的读入次数,通过多路归并输出结果时,使用输出缓存区暂存结果可以减少对输出文件的写入次数

  4. 多路归并的使用减少了从输入文件读取数据的次数。如果我们使用二路归并算法,意味着一次归并仅仅只是将两个中间文件合成为了一个中间文件而已,新生成的中间文件还要继续参与后续的归并排序(即多层级多路归并),也就是说中间文件中的数据被读取了多次,一般情况归并的路数应该尽量等于中间文件的数目,当然如果数据量实在太大生成的中间文件数目太多,导致数据无法载入(数据段大小*中间文件数目>可用内存容量),你就需要在减小数据段大小还是减小中间文件数目之间作出权衡

  5. 关于中间文件的优化。虽然流程图中给出了多个中间文件来存放个块已排序的数据,但实际上你也可以将各个已排序数据块存放在一个中间文件中(读取时可以依据数据块大小以及数据块编号找到对应数据块内容),当然这样做并不会减少磁盘I/O次数,只是减少了排序期间程序占用的文件句柄资源而已。

  6. 使用精简的数据结构来表示待排序的数据。编程珠玑中给出了位向量(后文会有介绍)的方案来表示待排序的数据,简化数据的表示方案相当于给内存进行扩容,并可同时提高数据处理效率,可以说使用一种合适的数据结构来描述目标数据不仅仅在外排序中十分重要,甚至在整个计算机领域中都是极为重要的,虽然将这个优化方案放在了最后,但其实该优化方案是应该最先应用的,因为也许通过位向量/图组织数据后可以一次性内排序数据

位向量以及位图

可以将位向量理解为一维数组,位图为二维数组,不同于普通数组的地方在于前者的元素取值一般为0或1,用来表示元素存在与否,元素间关系存在与否,例如:集合数据集就很适合使用位向量来表示,假设集合A的值域为0到9的自然数,那么A={0, 2, 6, 9},可以使用位向量a="1001000101"来表示该集合,0/1值用以表示该位置对应的值是否在集合中出现。数据结构中的图,很适合使用位图来表示,假设有向图G=(V, E), V={0, 1, 2}, E={(0, 1), (1, 2)},可以使用位图g[3][3]={{0, 1, 0}, {0, 0, 1}, {0, 0, 0}}来表示

那么我们为什么要使用位向量/位图来表示数据?

简化数据表示方式不仅仅可以降低对内存容量的需求,同时可以提高数据处理的速度,就以本文中外排序的问题为例,大文件中存放的是7位(十进制)的整数,如果我们使用字符串来表示的话,每个整数将消耗7bytes,如果我们使用整数类型(4字节的)来表示的话(好在我们这里是7位的整数,无符4字节整型最多可以表示11位的整数),每个整数将消耗4bytes,那如果使用位向量呢?问题中的值域决定了大文件所需的总空间,也就是说位向量的大小为107,如果我们的位向量使用字符串来实现的话,大文件中的每个数据仅仅消耗1byte,再进一步讲,如果我们使用比特位来实现位向量的话,每个数据仅仅消耗1bit,从7bytes缩减到1bit,相当于对内存扩容了56倍

位向量/位图是如何用程序来实现的?

正如上面提到的位向量可以通过比特位来实现,同样位图也可以通过比特位实现,唯一的不同在于位图在索引数据时需要自己在线性地址和二维地址间进行转换,当然我们并非强制使用比特位来实现位向量/位图,只不过比特位的方式是最节约空间的,如果你的空间较为充裕,你完全可以使用数组来实现位向量/位图(使用数组的另外一个好处是,你可以表示数据出现的重复次数)

位向量/位图适合表示哪些数据?

一定要有个明确的意识,根据实际问题的应用场景来选取合适的数据结构,不要拿个锤子看到什么都是钉子,位向量/位图也有自身的局限性,一般用于表示稠密的数据,数据结构中图的实现方案就很好的体现了这一点,稠密图的则使用二维数组(即位图)实现,而稀疏图使用邻接表来实现则更好

如何使用位向量/位图来排序呢?

首先,你要明白位图/位向量仅仅只是一种数据结构而已,它们并非排序算法本身,只不过由于该数据结构的特殊性,使得它们很适用于排序的场景,以编程珠玑中外排序问题为例,使用位向量的排序算法分为三步:

  1. 初始化位向量,即关闭(设置为0)位向量的所有位

  2. 从输入文件中读入数据,将相应位打开(设置为1)

  3. 从前往后遍历位向量,如果位是打开的,则输出该位表示的数据(一般就是该位的索引)

**注:**因为位向量可以用较少的空间表示较多的内容,所以该排序算法很适用于外排序的场景,如果可以使用位向量一次性装入大文件数据,那排序就轻而易举了,这就是为什么我们要说使用合适的数据结构表示大文件中的数据是应该被最先考虑的,此外要注意虽然该算法可以解决外排序问题,但该算法并不是归并算法

多路归并的实现

其实常用的内排序归并算法是两路归并的,在这种情况下只需要简单比较两个元素即可选出最小值,但若是多路归并呢?如何以较小的代价选取多个元素中的最小值是问题的关键,试想一下,如果使用快速排序算法来选取最小值,每当有新值添加进来时就要进行一次快排,换句话说,我们忽略了选出最小值后其余元素已被排序的事实,那么如何在选出最小值时利用之前排序的成果是我们要解决的问题(或者说引入新值时对之前排序成果的影响较小),如果此时你联想到了堆排序,恭喜你,已离成功近了一步,我们先来回顾一下堆排序的过程,首先对n个元素进行最小堆构建,当弹出堆顶后重新调整堆,直到堆为空,这里我们的关注点是在弹出堆顶后堆的重新调整是如何完成的,具体做法是:将堆尾部元素移到根部,从根部往下比较将小值交换到父节点,也就是说堆排序重构堆时最多只需从根部沿某一分支遍历到叶节点,这正是我们在多路归并中所希望的,选出最小值后对已排序数据的影响尽可能的小,那多路归并能不能使用堆排序呢?从理论上来讲是可以的,我们可以将待排序的数据段接入堆的叶节点(并在节点中表明所属的数据段),当弹出堆顶后再从堆顶对应的数据段载入数据,若对应的数据段为空,则仅弹出堆顶并重构堆,直到堆空,也就是说使用堆排序来实现多路归并是可行的(时间性能上是可接受的),那从实际应用的角度讲呢?我们在多路归并中使用的是堆排序的一种变体,即竞赛树

编程珠玑之第一章问题集

  1. 如何生成k个小于n且不重复的随机数(C语言中的库函数rand()返回的最大值是32767)?

  2. 如果将外排序示例问题中“每个数字不能重复”改为“每个数字最多出现10次“,该如何设计算法?

  3. 假设示例中的数据集表示的是7位数字的电话号码,若数据集是由区号+电话号码组成的,该如何排序大文件,以及如何快速的从中检索某个号码是否已经被占用了?

  4. 如何通过使用更多的空间来避免位向量排序的初始化阶段?

Xiao Wenbin
Xiao Wenbin
Natural Language Processing Engineer

My research interests include machine learning, information retrieval and natural language processing.