每周学点大数据 | No.12数据流中的频繁元素

No.12期

数据流中的频繁元素

Mr. 王:我们再来讲一个例子,数据流中的频繁元素。我们先来说说大数据的数据流模型。

小可:数据流,是流动的数据的意思吗?和我们前面说的水库抽样是不是很像?

数据流

Mr. 王点点头,说:嗯,其实水库抽样也是以数据流的思想来处理的。顾名思义,数据流意味着数据在流动,数据会不断地到达计算系统进行处理,这意味着一个数据只能被扫描一次,一旦处理过或者在内存中被放弃,就不能再访问了。你想想看,这在复杂度上意味着什么?

小可想了想,说:超过O(n)的算法肯定是不行的,只能寻找亚线性算法了。

Mr. 王:没错,而且数据流模型的数据是源源不断到来的,比如我们使用一个传感器进行感知,它就会按照一定的采样频率进行数据采集。其实传感器获得的数据就是一个典型的数据流,如果传感器一直在工作,我们就会得到源源不断的数据。但是不管是传感器使用的内存还是其他存储介质都不是无限的,这是符合客观现实的。所以对数据流进行处理,要求我们所使用的内存必须是亚线性的,最好是和数据量无关的。

小可:就像水库抽样一样吧,内存中随时保存着的都是对前面数据流的一个均匀抽样,而且所使用的内存有限,不论来了多少数据,都只保存k个,也是与数据量无关的。

Mr. 王:很好,这样用于概括数据的数据结构叫作数据概要,我们用有限的、与数据量无关的内存空间来维护这个数据概要,就是要对相关性质的当前状态做出一个有效估计。

数据流模型

我们说数据流模型是适用于大数据的,因为它仅顺序扫描数据一次,而且它的内存是亚线性的。数据流通常是来自某个域中元素的序列,<x1, x2, x3, x4,...>。

小可:这个序列里为什么没有末项xn

Mr. 王:因为数据是源源不断的,所以没有末项。好了,我们来总结一下数据流模型的特点:

(1)数据流通常是来自某个域中元素的序列,< x1, x2, x3, x4,...>。

(2)数据量是远大于内存容量的,这意味着无法将所有的数据都放进内存中。内存的规模一般为O(logkn) 或者O(na),显然a<1。

(3)要快速处理每一个数据,因为数据会快速地源源不断地到来,这也是很必要的一点。

小可:嗯,那我们将大数据视为数据流模型,可以拿来计算什么呢?

Mr. 王:应用就有很多了,有sum(求和)、max(最大值)、min(最小值)、count(计数)、avg(平均数)这样的基本统计量,还有比如中位数、频繁项、分析、挖掘、预警等。

我们还是举个具体的例子吧,这里有一组数字:32,12,14,32,7,12,32,7,6,12,4。

Mr. 王:你说说看,前面提到的统计量哪些是比较容易计算的?

小可:前面讲解选择排序时,讲过求min的方法,我觉得那个方法同样适用于数据流,只要拿出一个变量来保存当前的最小值,发现比它更小的就将其替换掉;max与之同理。求和sum也是很容易的,只要用一个变量来保存当前的加和,每到来一个数据,就把它加进这个变量里。至于count,初始化为0,然后每到来一个数据,就把它加1。如果要求平均数avg,就同时维护sum和count作商。

Mr. 王:很好,可以看出,这样的数据概要是单个值,同时它也是一个可合并的值。在这里,“可合并”就是指两部分数据流的数据概要可以直接通过诸如累加和比较这样的操作合并成整个数据流的概要。

小可:嗯,比如我们要求200个数据的最大值,前100个数据的最大值和后100个数据的最大值的较大者,就是200个数据的最大值。

Mr. 王:现在我们来处理一个复杂一点的问题——频繁元素。为了研究方便,我们用n来表示不同元素的个数,用m来表示元素的总个数。你先来想一想,如果要求出一个精确解的话,可以用什么方法?

小可:可以用这样的方法:

(1)为每一个单独元素设置一个计数器。

(2)当处理一个元素时,增加相应的计数器。

Mr. 王:这样做有什么问题吗?

小可:如果每个元素都有自己的计数器,就需要有n个计数器,这样没有满足o(n)的要求,相当于内存需要存储所有的数据,这对于数据流来说是不能实现的。

Mr. 王:嗯,所以我们提出如下的方法:

(1)处理一个新到来的元素x 时;

(2)If已经为其分配计数器,增加之;

(3)ElseIf 没有相应的计数器,但计数器个数少于k,为x 分配计数器k,并设为1;

(4)Else 所有的计数器值减1,删除值为0 的计数器。

这个算法称为MisraGries(MG)算法。第一种情况,如果内存中已经有新到来元素的计数器,则只需要将其值加1即可;第二种情况,如果还没有为新到来的元素提供计数器,并且内存没有被填满时,则可以为这个元素的计数器开辟新的空间;第三种情况,当新到来的元素没有被分配计数器,同时内存中的计数器个数已经达到了k个,也就是分配的内存空间已经被填满时,则将所有的计数器值减1,删除值为0的计数器,此时内存中就重新有位置了,我们再为这个新到达的元素分配一个计数器即可。当然,别忘了要将其置为1。

内容来源:灯塔大数据

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

原文发表时间:2016-11-04

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

2018.10.23NOIP模拟赛解题报告

比赛开场看T1一点思路都没有,不管怎么想都是\(O(n^2)\)的复杂度,做了好久终于发现自己傻逼了这就是个傻逼题。。

11030
来自专栏机器学习和数学

[数据结构和算法]《算法导论》动态规划笔记(1)

动态规划是求解最优化问题的方法,这类问题有很多可行解,每个解都有一个值,我们希望寻找具有最优值的解。我们称这个解为问题的一个最优解,而不是最优解,因为可能有多个...

408100
来自专栏mathor

LeetCode69. x 的平方根

 这道题直接一个return Math.sqrt就出来了,但是秉承着学习的心态,尝试着用二分法ac  首先要确定的就是左右区间,左区间是0无疑了,那么右...

22020
来自专栏章鱼的慢慢技术路

《算法图解》第一章笔记与课后练习_二分查找算法

23040
来自专栏沈唁志

PHP使用递归算法查找子集获取无限极分类等实操

递归函数是我们常用到的一类函数,最基本的特点是在函数或子过程的内部,直接或者间接地调用自己的算法,但必须在调用自身前有条件判断,否则无限调用下去,也就是所谓的死...

27530
来自专栏申龙斌的程序人生

参加steemit数学x程式大赛(第八回)

前一段时间参加了Steemit社区的两个活动,比如“接龙”创作大赛,五个人根据几张图片素材编出一篇小说,事先没有任何沟通,人员报名之后,顺序是随机指定的,我第一...

31960
来自专栏章鱼的慢慢技术路

《算法图解》第一章笔记与课后练习

39940
来自专栏小红豆的数据分析

小蛇学python(17)时间序列的数据处理

不管是在金融学、经济学的社会学科领域,还是生态学、系统神经的自然学科领域,时间序列数据都是一种重要的结构化数据形式。

21950
来自专栏机器之心

从七桥问题开始:全面介绍图论及其应用

选自Medium 作者:Vardan Grigoryan 机器之心编译 图论是计算机科学中最重要、最有趣的领域之一,同时也是最容易被误解的。本长文从图论最基础的...

42280
来自专栏Vamei实验室

纸上谈兵: 图 (graph)

图(graph)是一种比较松散的数据结构。它有一些节点(vertice),在某些节点之间,由边(edge)相连。节点的概念在树中也出现过,我们通常在节点中储存数...

227100

扫码关注云+社区

领取腾讯云代金券