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

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

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

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

　　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亿个整数，设计算法找到只出现一次的整数。

　　【分析】：

　　如果是有符号整数的话，范围为-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）。

　　【分析3】：

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

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