在线咨询
有事点这里
有事点这里
看不懂这篇文章?联系我们
("麦洛克菲"长期致力于内核安全的推广与普及,我们更专业!)
求职QQ群:223902435。讨论各种求职笔试面试问题
作者:admin 时间:2015-10-31
海量数据处理

一,海量数据处理的数据规模:

        1T = 1024G 

       1G = 10亿

       2G = 2*1000*1000*1000=20亿

       2^32=4*2^30 = 4G = 40亿

       1M = 1*1000*1000 = 100

 

       计算机存储单位一般用BKBMBGBTBPBEBZBYBBB来表示。

       1KB (Kilobyte 千字节)=1024B

       1MB (Megabyte 兆字节 简称“兆”)=1024KB

       1GB (Gigabyte 吉字节 又称“千兆”)=1024MB

       1TB (Trillionbyte 万亿字节 太字节)=1024GB,其中1024=2^10 ( 2 10次方)

       1PBPetabyte 千万亿字节 拍字节)=1024TB

       1EBExabyte 百亿亿字节 艾字节)=1024PB

       1ZB (Zettabyte 十万亿亿字节 泽字节)= 1024 EB

       1YB (Yottabyte 一亿亿亿字节 尧字节)= 1024 ZB

       1BB (Brontobyte 一千亿亿亿字节)= 1024 YB


二,海量数据处理常用算法:

 

       1Bloom filter

       适用范围:可以用来实现数据字典,进行数据的判重,或者集合求交集合求交集

       2Hashing

       适用范围:快速查找,删除的基本数据结构,通常需要总数据量可以放入内存。

       3bit-map

       适用范围:可进行数据的快速查找,判重,删除,一般来说数据范围是int10倍以下

       4.堆

       适用范围:海量数据前n大,并且n比较小,堆可以放入内存

       5.分区划分

       适用范围:第k大,中位数,不重复或重复的数字

       6.倒排索引(Inverted index)

       适用范围:搜索引擎,关键字查询

       7.外排序

       适用范围:大数据的排序,去重

       8

       适用范围:数据量大,重复多,但是数据种类小可以放入内存

       9.分布式处理 mapreduce

       适用范围:数据量大,但是数据种类小可以放入内存

       基本原理及要点:将数据交给不同的机器去处理,数据划分,结果归约。

 

三,海量数据处理实际例子:

 

       1.海量日志数据,提取出某日访问百度次数最多的那个IP

       2.搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。假设目前有一千万个记录(这些查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多,也就是越热门。),请你统计最热门的10个查询串,要求使用的内存不能超过       

        3.有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M。返回频数最高的

       4.有10个文件,每个文件1G,每个文件的每一行存放的都是用户的query,每个文件的query都可能重复。要求你按照

       5.给定ab两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出ab文件共同的

       6.在2.5亿个整数中找出不重复的整数,注,内存不足以容纳这

       7.给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中?

       8.怎么在海量数据中找出重复次数最多的一个?

       9.上千万或上亿数据(有重复),统计其中出现次数最多的钱N个数据。