海量数据处理专题(九)——外排序

【引言】

在数据结构的课程上,我们学习了不少的排序算法,冒泡,堆,快排,归并等。但是这些排序方法有着共同的特点,那就是所有的操作都是在内存中完成的,算法过程中不需要IO,这就使得这样的算法总体上速度比较快,但是也随之出现了一个问题:当需要排序的数据量异常的大的时候,以上的算法就显得力不从心了。这时候,你需要一种另外的排序算法,它的名字叫“外排序”。

通常的,设备的内存读取速度要比外存读取速度快得多(RAM的访问速度大约是磁盘的25万倍),但是内存的容量却要比外存小很多,当所有的数据不能在内存中完全放下的时候,就需要使用到外排序。这是外排序的一个显著特征。

【什么是外排序】

外排序其实是采用一种分治(Divide and conquer algorithm)的算法设计思想,将一个大问题划分成相对独立的若干个小问题,解决小问题,得到小问题的答案,然后合并小问题的答案,最终得到原始大问题的答案。

在这里,我们举一个外排的典型例子,二路外部归并排序,假设我们有一个大文件,里面是待排序的数据,一共N个,这些数据在内存中放不下。排序过程如下:

  1. 将该大文件分割成大小为m的文件(m小于可用内存大小)
  2. 将这些小文件依次读入内存,在内存中采用任一种排序算法排序并输出文件F1,F2….Fn。(其实可以和第一步合并,可以省一次IO)
  3. 分块快读取两个已经排完序的文件Fi和Fi+1,由于两个文件已经排完序,这里可以用归并排序,将两个文件排序完毕,并写入文件。(这个过程就好比有两队人马将其合并为一对一样)
  4. 重复过程3,直到剩余文件数为1。

以上就是二路外部归并排序的基本思路,毫无疑问,这种排序算法需要读取外存(IO)次数为log(2,N/m),这时候算法的性能瓶颈已经不在内存中排序的时间复杂度上,而是内外村交换数据IO的次数了。这里我补充一句,各种操作的性能差别:

读取网络 > 磁盘文件IO > 读取数据库 > 内存读取

这个可谓是程序性能的黄金法则,各位在写对性能要求比较高的程序时一定要考虑。

好,言归正传,二路归并排序这个算法的性能时比较低的。因此就有了多路归并排序算法,其IO的次数为log(b, N/m),其中b为几路归并。这个可以参考以下地址:

http://zh.wikipedia.org/wiki/外排序

【实战训练】

淘宝不同用户的浏览log有上千万or亿数据(有重复),统计其中有相同浏览爱好的用户。

转载请注明出处:http://diducoder.com/mass-data-topic-9-external-sort.html 

海量数据处理专题(九)——外排序》上有1条评论

  1. Pingback引用通告: 海量数据处理专题(一)——开篇 | 帝都码农

发表评论

电子邮件地址不会被公开。 必填项已用*标注