当前位置:   article > 正文

干货:经典的大数据问题实例合集!_大数据问题案例

大数据问题案例

 大数据几乎是新兴行业当中绕不开的话题了,当真正接触或从事大数据以后,应该以什么思路去把这个不容易啃的硬骨头解决掉呢?跟随大圣众包威客平台的脚步一探究竟吧!

wKhQt1PWBqSEG-PpAAAAAI-EItA871.jpg

  一、解决大数据问题的主要思路

  不同的人,对大数据也有着不同的理解,从实际意义上看,大数据可以指种类多、流量大、容量大、价值高、处理和分析速度快的真实数据汇聚的产物。通常应用于存储空间、提高效率等问题上。而解决大数据问题的一般主要思想有如下:

  1.文件切分(将大文件切成若干个小文件进行处理);

  2.哈希切分;

  3.使用位图。

  二、结合实例,处理大数据问题

  1.在海量的日志数据中,提取出某日访问百度次数最多的那个IP;或在一个超过100G的IP地址文件中找出出现次数最多的IP地址。

  【分析】:

  这两个题是同类型的题。IP的数目还是有限的,最多有个2^32(42亿)个IP,而且应注意到IP是32位的。

  1byte=8位

  1KB=1024bytes(字节)

  1MB=1024KB

  1GB=1024MB

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

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

wKhQt1PWBqSEG-PpAAAAAI-EItA871_meitu_4.jpg

  【分析】:

  如果是有符号整数的话,范围为-2147483648~2147483647,无符号整数的话,范围为0~4294967296。有符号的,使用两个bitset,一个存放正数,一个存放负数。每个数使用两个位来判断其出现几次。00表示出现0次,01出现1次,10出现大于一次。

  比如说存放整数100,就将bitset的第100*2位设置为+1,当所有数放完之后,对每两位进行测试,看其值为多少。若是第i与i+1的值为01,则这个整数:i*2,在集合中只出现了1次,需要总共用bitnum=(2^31*2)个位表示,需空间为int[bitnum],即512M。

  3.当前有40亿个不重复的、没排过序的unsignedint的整数,也有一个任意数,如何快速判断这个任意数是否在那40亿个数当中。

  【分析1】:

  40亿个整数差不多相当于全部整数,需要总共用(2^32)个位表示,需空间为int[bitnum],即512M。申请512M的内存,一个bit位代表一个unsignedint值。再读入40亿个数,设置相应的bit位,读入要查询的数,查看相应bit位是否为1。为1表示存在,为0表示不存在。

  【分析2】:

  因为2^32为40亿多,所以这个任意数可能在,也可能不在其中。

  可以先把40亿个数中的每一个用32位的二进制来表示,假设这40亿个数是放在一个文件中的,再将这40亿个数分成两类:分别是最高位为0和最高位为1,并将这两类分别写入到两个文件中,其中一个文件中数的个数≤20亿,而另一个≥20亿(这相当于折了),再与要查找的数的最高位比较并进入相应的文件再查找。然后把这个文件为又分成两类:分别是次最高位为0和次最高位为1,并将这两类分别写入到两个文件中,其中一个文件中数的个数≤10亿,而另一个≥10亿(这相当于折半了),再与要查找的数的次最高位比较并接着进入相应的文件再查找……如此类推,便能找到结果,而且时间复杂度仅为O(logn)。

1465571460-5295-2081.jpg

  【分析3】:

  此例还可以使用位图方法。位图法是常见编程任务之一,它能够判断整形数组是否存在重复判断集合中存在重复。当集合中数据量比较大时,通常希望少进行几次扫描,这时双重循环法就不可取了。但是,位图法就比较适合这种情况。

  它的做法是,按照集合中最大元素max创建一个长度为max+1的新数组,然后再次扫描原数组,遇到几就给新数组的第几位置上1,如遇到5就给新数组的第六个元素置1,这样下次再遇到5想置位时发现新数组的第六个元素已经是1了,这说明这次的数据肯定和以前的数据存在着重复。它的运算次数最坏的情况为2N。如果已知数组的最大值,即能事先给新数组定长的话效率还能提高一倍。




声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/黑客灵魂/article/detail/893365
推荐阅读
相关标签
  

闽ICP备14008679号