关于 海量日志数据,提取出某日访问百度次数最多的那个IP 的疑问!
时间:2011-09-01
来源:互联网
海量日志数据,提取出某日访问百度次数最多的那个IP。
首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中。注意到IP是32位的,最多有个2^32个IP。同样可以采用映射的方法,比如模1000,把整个大文件映射为1000个小文件,再找出每个小文中出现频率最大的IP(可以采用hash_map进行频率统计,然后再找出频率最大的几个)及相应的频率。然后再在这1000个最大的IP中,找出那个频率最大的IP,即为所求。
算法思想:分而治之+Hash
1.IP地址最多有2^32=4G种取值情况,所以不能完全加载到内存中处理;
2.可以考虑采用“分而治之”的思想,按照IP地址的Hash(IP)%1024值,把海量IP日志分别存储到1024个小文件中。这样,每个小文件最多包含4MB个IP地址;
3.对于每一个小文件,可以构建一个IP为key,出现次数为value的Hash map,同时记录当前出现次数最多的那个IP地址;
4.可以得到1024个小文件中的出现次数最多的IP,再依据常规的排序算法得到总体上出现次数最多的IP;
关于 第二步 的疑问,"IP地址的Hash(IP)%1024值" 是什么意思,是对所有IP地址进行排序,并分别统计每个IP出现的个数? 如果不是这样,那么如果直接分成1024个文件,就可能会出现某一个IP在每一个子文件中都存在,但不是每一个文件中出现次数最多的,这样是否有可能造成结果不准确,当然这肯定是我没有理解正确。
还请大家指点一下迷津! 谢谢!
首先是这一天,并且是访问百度的日志中的IP取出来,逐个写入到一个大文件中。注意到IP是32位的,最多有个2^32个IP。同样可以采用映射的方法,比如模1000,把整个大文件映射为1000个小文件,再找出每个小文中出现频率最大的IP(可以采用hash_map进行频率统计,然后再找出频率最大的几个)及相应的频率。然后再在这1000个最大的IP中,找出那个频率最大的IP,即为所求。
算法思想:分而治之+Hash
1.IP地址最多有2^32=4G种取值情况,所以不能完全加载到内存中处理;
2.可以考虑采用“分而治之”的思想,按照IP地址的Hash(IP)%1024值,把海量IP日志分别存储到1024个小文件中。这样,每个小文件最多包含4MB个IP地址;
3.对于每一个小文件,可以构建一个IP为key,出现次数为value的Hash map,同时记录当前出现次数最多的那个IP地址;
4.可以得到1024个小文件中的出现次数最多的IP,再依据常规的排序算法得到总体上出现次数最多的IP;
关于 第二步 的疑问,"IP地址的Hash(IP)%1024值" 是什么意思,是对所有IP地址进行排序,并分别统计每个IP出现的个数? 如果不是这样,那么如果直接分成1024个文件,就可能会出现某一个IP在每一个子文件中都存在,但不是每一个文件中出现次数最多的,这样是否有可能造成结果不准确,当然这肯定是我没有理解正确。
还请大家指点一下迷津! 谢谢!
作者: zlxx5427 发布时间: 2011-09-01
关于 第二步 的疑问,"IP地址的Hash(IP)%1024值" 是什么意思,是对所有IP地址进行排序,并分别统计每个IP出现的个数?
一个IP就是一个uint32啊 %1024就是对1024取余啊,跟排序无关
如果不是这样,那么如果直接分成1024个文件,就可能会出现某一个IP在每一个子文件中都存在,但不是每一个文件中出现次数最多的,这样是否有可能造成结果不准确,当然这肯定是我没有理解正确。
一个IP(uint32)%1024只会有1024种可能,一个IP只会有1个结果啊,怎么会分配到不同的文件?
一个IP就是一个uint32啊 %1024就是对1024取余啊,跟排序无关
如果不是这样,那么如果直接分成1024个文件,就可能会出现某一个IP在每一个子文件中都存在,但不是每一个文件中出现次数最多的,这样是否有可能造成结果不准确,当然这肯定是我没有理解正确。
一个IP(uint32)%1024只会有1024种可能,一个IP只会有1个结果啊,怎么会分配到不同的文件?
作者: oo 发布时间: 2011-09-01
hash可能是多级的,取模1024应该也属于哈希算法的一部分。
作者: asmlearn 发布时间: 2011-09-01
相关阅读 更多
热门阅读
-
office 2019专业增强版最新2021版激活秘钥/序列号/激活码推荐 附激活工具
阅读:74
-
如何安装mysql8.0
阅读:31
-
Word快速设置标题样式步骤详解
阅读:28
-
20+道必知必会的Vue面试题(附答案解析)
阅读:37
-
HTML如何制作表单
阅读:22
-
百词斩可以改天数吗?当然可以,4个步骤轻松修改天数!
阅读:31
-
ET文件格式和XLS格式文件之间如何转化?
阅读:24
-
react和vue的区别及优缺点是什么
阅读:121
-
支付宝人脸识别如何关闭?
阅读:21
-
腾讯微云怎么修改照片或视频备份路径?
阅读:28