大数据问题解决方案

声明:  本文中有两个简单的大数据问题，只给出了解决方案的大概描述。

1. 给定100亿个整数，设计算法找到只出现⼀次的整数?

问题分析：

整数的范围总共有42亿左右。如果按照最原始的方法，给每一个整数分配一个计数器的话，计数器设为整形，建立以42亿整数作为索引和对应的计数器当成元素的数组，然后一个个的遍历100亿个整数，遍历完成后在统计只出现一次的整数。显然这个方法对空间的浪费非常大。42亿个整形，相当于160亿的字节，总共占16G内存，个人电脑上根本满足不了，就算是一个字节也要占用4G内存，这也有点不现实。所以就要利用位图的知识。

解决方案：

我们可以利用位图来表示。不过题目是要找到只出现一次的整数，整数的出现次数可以有0 , 1 , >1这三种，所以不能只用一位来表示一个数字出现次数的状态。 根据题意，一个数出现次数的状态最少要有三种，因此需要用两位来表示一个数字出现次数的状态。0 表示这100亿整数中没有出现这个数; 1 就是我们要找的;  >1 表示出现次数不只一次， 其实当数字出现次数等于2（即二进制10）时我们就不用再管了， 因为题目只要求我们找到只出现一次的整数。这样的话42亿个数，每个数的状态用两位表示，大概占用10亿个字节，也就是1G。占用内存明显小了很多。如果感觉1G内存仍然很大，可以这样， 首先统计前21亿个数中只出现一次的数字，遍历完之后再次遍历统计21亿~42亿之间只出现一次的数字。只不过第二次统计时对应的位置要减去21亿，使用的是相对位置。如果这样就占内存21亿*2位 = 42亿位 = 5亿 字节 = 500M， 内存又小了。当然可以使用此方法再次细分，内存会占用更少，只不过要利用相对位置， 同时缺点就是也更浪费时间，因为要多遍历几次。

2. 给⼀个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？

问题分析：

IP地址总共有32位，共有差不多42亿个。若统计按照每个IP地址都给一个计数器，每个计数器是一个整型，那就需要42亿*4 = 168亿个字节，即大概占用17G的内存，显然不行。那我们就想办法让计算量变小。采用切分的方法。

解决方案：

把总共100G的文件切分成100份。首先要有100个容器，编号0~99， 然后把每一个IP放到它对应的值模100后对应的容器内。分配完成后，如果两个IP相同，那就肯定在同一个容器里，且每一个容器最多只能有4200万个不同的IP，当然每个容器大小是不定的。

此时在统计每一个容器中出现次数最多的IP，然后100个容器得到的结果再选出最大的就行了。统计一个容器时给每一个不同的IP分配一个计数器，那总共就占用4200万*4=1.6亿字节=0.16G，这是可以的，但需要多遍历一次。

最后

以上就是文艺咖啡豆为你收集整理的大数据问题解决方案的全部内容，希望文章能够帮你解决大数据问题解决方案所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。