每周学点大数据 | No.22 外排序

No.22期

外排序(一)

Mr. 王:接下来我们看一看在磁盘算法中一个比较典型的例子——外排序。

小可:那什么又是外排序呢?

Mr. 王:外排序是相对内排序而言的,当要排序的数据量无法被全部装进内存时,我们就需要用到外排序,此时有大量的数据被存在硬盘里,无法直接进行操作,必须先以块为单位读进内存中。

为了更好地理解大数据中的归并排序,我们先从内存中的归并排序说起。该算法被称为“归并排序”或者“多路归并排序”,其基本思想就是,先将整个数组划分为多组,保证每一组内是有序的,然后相邻的两组之间进行“归并”,使得产生的更大的组也是有序的,直到组的大小等于数组的大小。

归并排序体现了一个重要的算法思想——分治法。分治法是设计很多算法时一种有效的策略。

对于一个比较大、复杂的问题,我们很难一下子将其解决,这时就尝试采用将大的问题逐渐划分为小的问题,这些小的问题叫作子问题,对于子问题,求解起来往往会变得容易一些。

当然,我们还可以对子问题进行进一步的划分,划分成更小的子问题,在很多问题中,当子问题被划分得足够小时,就可以使用很简单的方法解决或者直接得到解决了。当这些子问题有效地得到解决时,我们就可以按照子问题和原问题的关系逐步将子问题的解进行合并,从而得到原来问题的解。

小可:这也符合我们日常生活中处理问题的思路。对于一个比较棘手的问题,我们会尝试将其分成多个较小的部分,再逐个击破,最后把各部分的解决方案拼到一起,就得到了原来那个大问题的解。

Mr. 王:归并排序其实就是分治法的一种典型体现,在二路归并排序中,首先要将整个乱序的序列划分为两路,然后分别对两路进行一个归并排序。注意,这个过程会递归地进行下去。也就是说,对划分出来的两路继续执行划分,变成四个部分,再从四个部分进行划分,变成八个部分,依此类推。

最后直到整个分成了只含有一个元素的序列时,它显然就已经排好序了,我们再把这些排好序的序列进行逐级合并,合并成长度为2,4,8,16 的序列。

小可:其实划分这个步骤非常容易做,关键就在于合并这个步骤怎么解决,怎么把两路已经排好序的序列合并到一起,成为一个仍然有序的序列呢?

Mr. 王拿出两组扑克牌放在桌面上,说:想一想,假设我们有两个有序的数字卡牌序列,分别是2468 和1357,我们要如何将其变成一组有序的数列,即12345678 呢?

在归并排序的合并中,我们可以用两个硬币来模拟移动的指针。首先,我们把两个指针分别放在两个序列的第一张牌上,由于两路都是有序的,所以这两张牌一定都是两路中最小的。

但这两张牌也是有大小关系的,不难想到,这两张牌里面最小的一定是所有8 张牌里面最小的。根据排序的问题定义,按照从小到大的顺序排列,所以第一次我们希望能够找出序列中最小的那个数。

于是,我们比较两个硬币所在的扑克牌,发现1 比2 小,所以取出1,放在外面,然后将硬币向右移动一个位置,放在3 上面。现在我们要找出8 张牌中第二小的。

小可:从8 张牌中拿出了最小的,那么剩下的7 张牌中最小的就是第二小的,所以我们只要找到剩下的7 张牌中最小的就可以了。方法还是和前面的一样,因为现在的两个硬币依然在两组数中最小的两个数上,只要比较它们的大小就可以了。一个是2,一个是3,所以取出2。

Mr. 王:很好,但别忘了将硬币再向右移动一个位置,此时在3 和4 上面。我们取出3,再将硬币向右移动。不断地进行这个步骤,最后就会发现,我们取出扑克牌的顺序刚好就是12345678。这样就非常有效地将两个大小为4 的序列合成一个大小为8 的序列,而同时满足了这个大小为8 的序列仍然有序这一要求。

小可:那从1 到2,2 到4,4 到8,8 到16 都可以用这个方法进行操作实现,所以对于任意的序列长度n,我们都可以用这个方法进行排序了。嗯,内存中的归并排序方法我基本上搞懂了。

Mr. 王:别急,我们先来看看这个算法的时间复杂度如何。

小可:这个可有点复杂,要怎么分析呢?

Mr. 王:其实要求解这类问题的时间复杂度,需要用到算法设计分析理论中的一个重要定理,叫作Master 定理,这是一个可以求解递归式的复杂度的定理。不过,今天我们尝试用一种比较直观的方法进行分析。首先看一下这个图:

在最后一轮中,将两个长度为n/2 的序列进行了归并,合并成长度为n 的序列。每个元素被访问了几次?

小可:根据我们前面说过的合并方法,每个元素实际上都被访问了常数次,因为就是做了一个简单的比较,所以应该是cn 次。

Mr. 王:那么倒数第二轮呢?

小可:在倒数第二轮中,有4 个序列被合并成2 个,其中一个合并过程有n/2 个元素参与,所以应该是cn/2,这样的过程应该有两个,所以依然是cn 次。

Mr. 王:由此发现,不管有多少个序列参与归并,其实在每一轮的归并中,都是访问了所有的元素常数次,每一轮都进行了cn 次的操作。这意味着归并排序中每一轮的复杂度都是O(n)。

小可:这个我懂了,只要知道整个归并排序进行了多少轮,再乘以O(n) 就可以了。

Mr. 王:很好,思路是非常正确的。现在我们来观察一下合并这个过程。

Mr. 王指着那个模拟合并过程的图,说道:如果将这里的每一个序列都看作一个节点,将图中的箭头线看作边,那么这是一个什么特殊的图?

小可恍然大悟,说:这是一棵树!!

Mr. 王:不难看出,树的每两层之间的边,就代表了进行一次归并。也就是说,树的高度-1就是进行归并的次数。

小可:没错,所以我们只要知道树的高度是多少就行了!

Mr. 王:好,这是一棵满二叉树,它有n 个叶子节点,这课树的高度是多少呢?

小可:满二叉树的内部节点数量为叶子节点数量-1,所以这棵树有2n-1 个节点;而一棵有N 个节点的树的高度是h=O(logN),所以就是h=O(logn)。

Mr. 王:综合起来,归并排序的时间复杂度就是O(logn)·O(n)=O(nlogn)。前面我们提过,基于比较的排序算法,它的时间复杂度下界是O(nlogn)。这说明它已经是一个非常高效的算法了。

归并排序的好处不仅仅是它的效率高,更重要的是它能够非常有效地应用在外排序中。在现实生活中,需要排序的数据量有时候是很大的,当内存中无法容纳这么大的数据量时,我们就要尝试将这些数据存储在磁盘上,利用内存作为数据的暂存地进行排序。

小可:那么在外排序中,归并排序又该怎么做呢?

Mr. 王:此时我们就要思考如何充分地利用内存空间了。将整个数组分为多少路,要考虑内存能装下多少个磁盘块,我们要分的路数等于内存能装下的磁盘块数。也就是说,一定要保证每一路都有一块在内存中。

内容来源:灯塔大数据

原文发布于微信公众号 - 灯塔大数据(DTbigdata)

原文发表时间:2017-01-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏抠抠空间

算法基础

1184
来自专栏开发与安全

从零开始学C++之STL(四):算法简介、7种算法分类

一、算法 算法是以函数模板的形式实现的。常用的算法涉及到比较、交换、查找、搜索、复制、修改、移除、反转、排序、合并等等。 算法并非容器类型的成员函数,而是一...

2070
来自专栏SeanCheney的专栏

《Pandas Cookbook》第05章 布尔索引1. 计算布尔值统计信息2. 构建多个布尔条件3. 用布尔索引过滤4. 用标签索引代替布尔索引5. 用唯一和有序索引选取6. 观察股价7. 翻译SQ

第01章 Pandas基础 第02章 DataFrame运算 第03章 数据分析入门 第04章 选取数据子集 第05章 布尔索引 第06章 索引对齐 ...

2052
来自专栏CDA数据分析师

学会这8个(组)excel函数,轻松解决工作中80%的难题

文 | 兰色幻想-赵志东 函数是excel中最重要的分析工具,面对400多个excel函数新手应该从哪里入手呢?下面是实际工作中最常用的8个(组)函数,学会后工...

2017
来自专栏锦小年的博客

Python数据分析(2)-pandas数据结构操作

pandas是一个提供快速、灵活、表达力强的数据结构的Python库,适合处理‘有关系’或者‘有标签’的数据。在利用Python做数据分析的时候,pandas是...

26510
来自专栏前端儿

A+B Problem(V)

做了A+B Problem之后,Yougth感觉太简单了,于是他想让你求出两个数反转后相加的值。帮帮他吧

851
来自专栏杨建荣的学习笔记

Java随机数算法(一)(r11笔记第14天)

问:如何生成一个随机的字符串?答:让新手退出VIM 。 这可能也是随机字符的一种由来:) 我们今天要说的是随机数算法,这个我策划了好久,但是进展缓慢。...

4677
来自专栏数据结构与算法

1200 同余方程

1200 同余方程 2012年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目...

2874
来自专栏backend技术总结

PHP浮点数

上面输出的结果是57, 而不是58, 为什么呢, 因为 你看似有穷的小数, 在计算机的二进制表示里却是无穷的(鸟哥的原话),0.58用二进制后, 重新计算出来的...

2375
来自专栏阮一峰的网络日志

Reduce 和 Transduce 的含义

学习函数式编程,必须掌握很多术语,否则根本看不懂文档。 本文介绍两个基本术语:reduce和transduce。它们非常重要,也非常有用。 ? 一、reduce...

2817

扫码关注云+社区

领取腾讯云代金券