2019年海量数据处理方法总结.doc
《2019年海量数据处理方法总结.doc》由会员分享,可在线阅读,更多相关《2019年海量数据处理方法总结.doc(13页珍藏版)》请在三一文库上搜索。
1、海量数据处理方法总结104733 0-1 00姓名:彭军职业:oop,linux,embeded年龄:位置:武汉个性介绍:sun up_user.jpg up_user_pre.jpg OTHER 11 0165 11053 41 2星级BLOG 0djkpengjun#FFFFFF#187218 no-repeat _blank 122784 02009-10-14 11:38:11 123793 122784 2009-10-28 11:38:19 122770 02009-10-14 09:33:52 122911 02009-10-15 16:34:00 127156 122911 2
2、009-12-17 10:46:36 127837 122911 2009-12-25 16:06:42 127841 122911 2009-12-25 16:08:14 122796 02009-10-14 15:47:33 123273 02009-10-20 13:24:36 138244 02010-06-03 14:58:29 136282 02010-05-01 13:45:02 124642 02009-11-11 00:07:29 123295 02009-10-20 16:01:57 140894 02010-07-21 00:42:21 4825 02009-10-22
3、16:41:0020091014,20091015,20091020,20091021,20091022,20091023,20091027,20091028,20091030,20091031,20091103,20091104,20091105,20091106,20091111,20091112,20091113,20091117,20091119,20091123,20091124,20091127,20091130,20091202,20091203,20091204,20091207,20091208,20091209,20091211,2009121 2,20091215,200
4、91217,20091218,20091222,20091223,20091224,20091225,20091228,20091229,20091230,20091231,20100104,20100106,20100111,20100113,20100114,20100115,20100118,20100119,20100120,20100121,20100125,20100126,20100127,20100128,20100201,20100222,20100223,20100224,20100308,20100309,20100310,20100316,20100319,201003
5、24,20100328,20100401,20100409,20100421,20100425,20100501,20100504,20100513,20100524,20100525,20100602,20100603,20100609,20100613,20100614,20100617,20100618,20100627,20100628,20100701,20100704,20100706,20100707,20100719,20100720,2277368 140894 2010-07-21 00:56:24 2010-07-21 01:02:14 10 0下面是某同仁在baidu和
6、google的笔试中遇到的两道百度、google海量数据搜索算法题解Google和baidu,人家的数据量在那里摆着,他们的命题思路很明确,不要求具体语言,只要求程序的效率和可行性,题目大多数是关于海量数据搜索的算法问题。百度、google的海量数据搜索算法题1、有1亿个浮点数,请找出其中对大的10000个。提示:假设每个浮点数占4个字节,1亿个浮点数就要站到相当大的空间,因此不能一次将全部读入内存进行排序。2、有一篇英文文章(也就是说每个单词之间由空格分隔),请找出csdn着个单词出现的次数,要求效率最高,并写出算法的时间级。Peak Wong的海量数据搜索算法题解1、有1亿个浮点数,请找出
7、其中对大的10000个。提示:假设每个浮点数占4个字节,1亿个浮点数就要站到相当大的空间,因此不能一次将全部读入内存进行排序。其实占用内存不算大,可以接受.呵呵.既然不可以一次读入内存,那可以这么试试:方法1:读出100w个数据,找出最大的1w个,如果这100w数据选择够理想,那么最小的这1w个数据里面最小的为基准,可以过滤掉1亿数据里面99%的数据,最后就再一次在剩下的100w(1%)里面找出最大的1w个咯方法2:分块,比如100w一个块,找出最大1w个,一次下来就剩下100w数据需要找出1w个了.对于上面提到的找出100w个数据里面最大的1w个,说起来比较罗嗦,还是说说找到第1 w个大的数
8、字的方法:用快速排序的方法,分2堆,如果大的那堆个数N大于1w个,继续对大堆快速排序一次分成2堆,如果大堆个数N小于1w,就在小的那堆里面快速排序一次,找第10000-N大的数字;递归以上过程,就可以找到第1 w大的数.据说也是STL的search_n()的方法;参考上面的找出第1 w大数字,相信楼主就可以类似的方法找出前1w大数字了.第二个问题,其实很简单。假设不区分大小写,由于英文字母有26个,因此,可以将单词映射为数字。csdn被映射成:(c-a)*32*32*32+(s-a)*32*32+(d-a)*32+(n-a)即:(c-a)*(1 15)+(s-a)*(1 10)+(d-a)*(
9、1 5)+(n-a)大数据量的问题是很多面试笔试中经常出现的问题,比如baidu google腾讯这样的一些涉及到海量数据的公司经常会问到。下面的方法是我对海量数据的处理方法进行了一个一般性的总结,当然这些方法可能并不能完全覆盖所有的问题,但是这样的一些方法也基本可以处理绝大多数遇到的问题。下面的一些问题基本直接来源于公司的面试笔试题目,方法不一定最优,如果你有更好的处理方法,欢迎与我讨论。1.Bloom filter适用范围:可以用来实现数据字典,进行数据的判重,或者集合求交集基本原理及要点:对于原理来说很简单,位数组+k个独立hash函数。将hash函数对应的值的位数组置1,查找时如果发现
10、所有hash函数对应位都是1说明存在,很明显这个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字,因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进就是counting Bloom filter,用一个counter数组代替位数组,就可以支持删除了。还有一个比较重要的问题,如何根据输入元素个数n,确定位数组m的大小及hash函数个数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的情况下,m至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些,因为还要保证bit数组里至少一半为0,则m应该=nlg(1/E)*
11、lge大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。举个例子我们假设错误率为0.01,则此时m应大概是n的13倍。这样k大概是8个。注意这里m与n的单位不同,m是bit为单位,而n则是以元素个数为单位(准确的说是不同元素的个数)。通常单个元素的长度都是有很多bit的。所以使用bloom filter内存上通常都是节省的。扩展:Bloom filter将集合中的元素映射到位数组中,用k(k为哈希函数个数)个映射位是否全1表示元素在不在这个集合中。Counting bloom filter(CBF)将位数组中的每一位扩展为一个counter,从而支持了元素的删除操作。Spectra
12、l Bloom Filter(SBF)将其与集合元素的出现次数关联。SBF采用counter中的最小值来近似表示元素的出现频率。问题实例:给你A,B两个文件,各存放50亿条URL,每条URL占用64字节,内存限制是4G,让你找出A,B文件共同的URL。如果是三个乃至n个文件呢?根据这个问题我们来计算下内存的占用,4G=232大概是40亿*8大概是340亿,n=50亿,如果按出错率0.01算需要的大概是650亿个bit。现在可用的是340亿,相差并不多,这样可能会使出错率上升些。另外如果这些urlip是一一对应的,就可以转换成ip,则大大简单了。2.Hashing适用范围:快速查找,删除的基本数
13、据结构,通常需要总数据量可以放入内存基本原理及要点:hash函数选择,针对字符串,整数,排列,具体相应的hash方法。碰撞处理,一种是open hashing,也称为拉链法;另一种就是closed hashing,也称开地址法,opened addressing。扩展:d-left hashing中的d是多个的意思,我们先简化这个问题,看一看2-left hashing。2-left hashing指的是将一个哈希表分成长度相等的两半,分别叫做T1和T2,给T1和T2分别配备一个哈希函数,h1和h2。在存储一个新的key时,同时用两个哈希函数进行计算,得出两个地址h1key和h2key。这时需
14、要检查T1中的h1key位置和T2中的h2key位置,哪一个位置已经存储的(有碰撞的)key比较多,然后将新key存储在负载少的位置。如果两边一样多,比如两个位置都为空或者都存储了一个key,就把新key存储在左边的T1子表中,2-left也由此而来。在查找一个key时,必须进行两次hash,同时查找两个位置。问题实例:1).海量日志数据,提取出某日访问百度次数最多的那个IP。IP的数目还是有限的,最多232个,所以可以考虑使用hash将ip直接存入内存,然后进行统计。3.bit-map适用范围:可进行数据的快速查找,判重,删除,一般来说数据范围是int的10倍以下基本原理及要点:使用bit数
15、组来表示某些元素是否存在,比如8位电话号码扩展:bloom filter可以看做是对bit-map的扩展问题实例:1)已知某个文件内包含一些电话号码,每个号码为8位数字,统计不同号码的个数。8位最多99 999 999,大概需要99m个bit,大概10几m字节的内存即可。2)2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。将bit-map扩展一下,用2bit表示一个数即可,0表示未出现,1表示出现一次,2表示出现2次及以上。或者我们不用2bit来进行表示,我们用两个bit-map即可模拟实现这个2bit-map。4.堆适用范围:海量数据前n大,并且n比较小,堆可以放
16、入内存基本原理及要点:最大堆求前n小,最小堆求前n大。方法,比如求前n小,我们比较当前元素与最大堆里的最大元素,如果它小于最大元素,则应该替换那个最大元素。这样最后得到的n个元素就是最小的n个。适合大数据量,求前n小,n的大小比较小的情况,这样可以扫描一遍即可得到所有的前n元素,效率很高。扩展:双堆,一个最大堆与一个最小堆结合,可以用来维护中位数。问题实例:1)100w个数中找最大的前100个数。用一个100个元素大小的最小堆即可。5.双层桶划分适用范围:第k大,中位数,不重复或重复的数字基本原理及要点:因为元素范围很大,不能利用直接寻址表,所以通过多次划分,逐步确定范围,然后最后在一个可以接
17、受的范围内进行。可以通过多次缩小,双层只是一个例子。扩展:问题实例:1).2.5亿个整数中找出不重复的整数的个数,内存空间不足以容纳这2.5亿个整数。有点像鸽巢原理,整数个数为232,也就是,我们可以将这232个数,划分为28个区域(比如用单个文件代表一个区域),然后将数据分离到不同的区域,然后不同的区域在利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间,就可以很方便的解决。2).5亿个int找它们的中位数。这个例子比上面那个更明显。首先我们将int划分为216个区域,然后读取数据统计落到各个区域里的数的个数,之后我们根据统计结果就可以判断中位数落到那个区域,同时知道这个区域中的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2019 海量 数据处理 方法 总结
链接地址:https://www.31doc.com/p-2491436.html