发帖
雷达卡
三种经典的大数据问题
当今世界高速发展，我们要处理越来越多的数据信息，如何快速的从这些海量的数据中找到我们需要的数据呢？这就是大数据要处理的问题，下面就对这三种大数据问题进行分析吧。
一. 设计算法找到每日访问百度出现次数最多的IP地址?
分析：将所有的IP逐个写入到一个大文件中，因为当IP地址采用点分十进制的方式表示的时候是32位的，所以最多存在2^32个IP。可以采用映射的方式，比如模1000，将这个较大的文件映射为1000个小文件，再将每个小文件加载到内存中找到每个小文件中出现频率最大的IP(可以使用hash_map的思想进行频率统计);然后在这1000个最大的IP中找出那个出现频率最大的IP，就是出现次数最多的IP了。
算法思想如下：(分而治之+hash)
1).IP地址最多有2^32=4G个，所以不能直接将所有的IP地址加载到内存中
2).可以考虑采用”分而治之”的思想，就是将IP地址Hash(IP)%1024值，将海量IP分别存储到1024个小文件中，这样每个小文件最多包含(2^32)/(2^10)=4M个IP地址
3).对于每一个小文件，可以构建一个IP值为key,出现次数为vaue的hash_map，通过value的比较找到每个文件中出现次数最多的那个IP地址
4).经过上述步骤已经得到1024个出现次数最多的IP地址，再选择一定的排序算法找出这1024个IP中出现次数最多的那个IP地址
二.给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件的交集?
分析：我们知道对于整形数据来说，不管是有符号的还是无符号的，总共有2^32=4G个数据(100亿个数据中肯定存在重复的数据)，我们可以采用位图的方式来解决，假如我们用一个位来代表一个整形数据，那仫4G个数共占512M内存。我们的做法是将第一个文件里的数据映射到位图中，再拿第二个文件中的数据和第一个文件中的数据做对比，有相同的数据就是存在交集(重复的数据，交集中只会出现一次).
三.假定一个文件有100亿个整形数据，1G内存，如何找到出现次数不超过两次的数字?
分析：要解决这个问题同样需要用到位图的思想，在问题二中已经了解到采用位图的一个位可以判断数据是否存在，那仫找到出现次数不超过两次的数字使用一个位是无法解决的，在这里可以考虑采用两个位的位图来解决.
根据上述分析我们可以借助两个位，来表示数字的存在状态和存在次数，比如：00表示不存在，01表示存在一次，10表示存在两次，11表示存在超过两次;类似问题二的计算过程：如果一个数字占一位，需要512M内存即可，但是如果一个数字占两位，则需要(2^32)/(2^2)=2^30=1G内存;将所有数据映射到位图中查找不是11的所对应的数字就解决上述问题了。
题目扩展：其他条件不变，假如只给定512M内存该如何找到出现次数不超过两次的数字?
分析：将数据分批处理，假若给定的是有符号数，则先解决正数，再解决负数，此时512M正好解决上述问题.
京公网安备 11010802022788号
