经典的大数据问题 随着信息的高速发展，越来越多的数据信息等待处理，如何快速的从这些海量数据中找到你所需要的数据呢?这就是大数据的处理问题，下面我对几个经典的大数据问题进行分析~~~~ 一. 设计算法找到每日访问百度出现次数最多的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正好解决上述问题.
四.给两个文件，分别有100亿个query，我们只有1G内存，如何找到两文件交集?分别给出精确算法和近似算法!
分析：看到字符串首先应该反应过来的就是布隆过滤器，而问题四的近似算法就是采用布隆过滤器的方法，之所以说布隆过滤器是近似的算法，因为它存在一定
的误判(不存在是肯定的，存在是不肯定的);而要想精确判断字符串文件的交集，我们可以采用分而治之的方法：将大文件切分为一个一个的小文件，将一个又一个的小文件拿到内存中做对比，找到对应的交集。
1.布隆过滤器的近似解决办法：
根据不同的字符串哈希算法，可以计算出不同的key值，然后进行映射，此时可以映射到不同的位置，只有当这几个位全部为1的时候这个字符串才有可能存在(因为当字符串过多的时候可能映射出相同的位)，只有一个位为0，那仫该串一定是不存在的，所以说布隆过滤器是一种近似的解决办法。将第一个文件映射到布隆过滤器中，然后拿第二个文件中的每个串进行对比(计算出特定串的key，通过不同的哈希算法映射出不同的位，如果全为1则认为该串是两个文件的交集;如果有一位为0那仫该串一定不是交集).
在上面实现的布隆过滤器中引用了不同的哈希算法，有想研究哈希算法的的童鞋可参考各种字符串Hash函数>>>
本文地址：http://syank.xrbh.cn/quote/1285.html
迅博思语资讯 http://syank.xrbh.cn/ , 查看更多