首页>> 正文

大数据处理问题

来源:商群邮件营销时间:2016-11-10 06:33:52点击:1526

大数据 , 就是指种类多、流量大、容量大、价值高、处理和分析速度快的真实数据汇聚的产物。

通常会需要考虑存储空间是、效率等问题。解决大数据问题一般主要的思想,1.文件切分,(将大文件切成若干个小文件进行处理),2.哈希切分,3.使用位图。以下通过几个实例来进行进一步分析:

1、海量日志数据,提取出某日访问百度次数最多的那个IP。(或者:给一个超过100G的文件,文件中存放着iP地址,请找出其中出现次数最多的IP地址

思考: 这两个题是同一个题 IP的数目还是有限的, 最多有个2^32(42亿)个IP, 注意到IP是32位的。

1byte = 8位

1 KB = 1024 bytes (字节)

1 MB = 1024 KB

1 GB = 1024 MB
假设每个IP只出现一次,所需内存大概为(32*2^32)位,约为16个G左右如果内存足够大,就直接进行统计但是如果内存没有那么大,)我们可以将大文件切分成若干个小文件(假如为100个小文件),采用映射的方法,比如用IP地址模1000,这样同一个IP地址肯定会出现在同一个小文件中,再找出每个小文中出现频率最大的IP(可以采用hash_map进行频率统计,然后再找出频率最大的几个)及相应的频率。然后再在这1000个最大的IP中,找出那个频率最大的IP,即为所求。

2.给定100亿个整数,设计算法找到只出现一次的整数

思考: 如果是有符号整数的话,范围为-2147483648~2147483647 

无符号整数为0~4294967296 ,有符号的使用两个bitset,一个存放正数,一个负数。 每

个数使用两个位来判断其出现几次。00表示出现0次,01出现1次,10出现大于一次。

比如说存放整数100,就将bitset的第100*2位设置为+1,当所有数放完之后,对每两

位进行测试看其值为多少?若是第i为与i+1为的值为01,则这个整数:i*2,在集合中只

出现了1次。需要总共用bitnun=(2^31*2)个位表示,需空间为int[bitnum],即512M.

3.给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判

断这个数是否在那40亿个数当中?

方案1 :40亿个整数差不多相当于全部整数, 需要总共用(2^32 )个位表示,需空间为

int[bitnum],即512M. 申请512M的内存,一个bit位代表一个unsigned int值。读入40亿

个数,设置相应的bit位,读入要查询的数,查看相应bit位是否为1,为1表示存在,为0

表示不存在。

方案2 因为2^32为40亿多,所以给定一个数可能在,也可能不在其中;这里我们

把40亿个数中的每一个用32位的二进制来表示假设这40亿个数开始放在一个文件中。

然后将这40亿个数分成两类: 1.最高位为0 2.最高位为1 并将这两类分别写入到两

个文件中, 其中一个文件中数的个数<=20亿,而另一个>=20亿(这相当于折 );

与要查找的数的最高位比较并接着进入相应的文件再查找, 再然后把这个文件为又分成

两类: 1.次最高位为0 2.次最高位为1。 并将这两类分别写入到两个文件中,其中一个文

件中数的个数 <=10亿,而另一个>=10亿(这相当于折半了) ; 与要查找的数的次最

高位比较并接着进入相应的文件再查找。 ....... 以此类推,就可以找到了,而且时间复

杂度为O(logn)。

方案三 位图方法 ,使用位图法判断整形数组是否存在重复 判断集合中存在重复是

常见编程任务之一,当集合中数据量比较大时我们通常希望少进行几次扫描,这时双重

循环法就不可取了。( 位图法比较适合于这种情况,它的做法是按照集合中最大元素

max创建一个长度为max+1的新数组,然后再次扫描原数组,遇到几就给新数组的第

几位置上1,如遇到5就给新数组的第六个元素置1,这样下次再遇到5想置位时发现新数

组的第六个元素已经是1了,这说明这次的数据肯定和以前的数据存在着重复。它的运

算次数最坏的情况为2N。如果已知数组的最大值即能事先给新数组定长的话效率还能提

高一倍。)

欢迎大家继续关注慧邮件邮件营销平台,也可以在我们的慧邮件官网了解更多邮件营销技巧,大数据知识,也可以通过电话:400-666-5494联系到我们,更多精彩知识、活动等着你。

相关阅读

  • *真实姓名:
  • *手机号码:
  • 公司名称:
  • 咨询内容:

CopyRight © 2009 - 2020 All Right Reserved 备案号:闽ICP备15004550号-275

厦门书生企友通科技有限公司 QYT.com 版权所有