Chinaunix首页 | 论坛 | 博客
  • 博客访问: 356882
  • 博文数量: 135
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1106
  • 用 户 组: 普通用户
  • 注册时间: 2013-03-20 09:56
文章分类

全部博文(135)

文章存档

2017年(3)

2016年(18)

2015年(69)

2014年(39)

2013年(6)

我的朋友

分类: C/C++

2015-11-16 16:00:24

题目:每一个ip访问百度,其ip地址都会被记录到后台日志文件中,假设一天的访问日志有100G,求出一天中访问百度次数最多的ip地址,可以使用的内存大小是1G。

分析

  1. 首先解决大文件问题,也就是如何处理100G的一个大文件,这个通常的解决方法就是将大文件分解成许多小文件。我们可以通过对IP地址求hash然后对1024取模将一个100G的大文件分解成1024个小文件(file0,file1......file1023),注意这里的1024个文件并不是平均分的,也就是每个文件大小并不是(100G/1204)。当然我们考虑的时候可以假设文件是平均分的,那么每个文件大小为100M,这样一个100M的文件是可以全部读入大小为1G内存中。这样就解决了第一个文件太大不能一次读入内存的问题。
  2. 考虑到ip地址是32为,那么总共有2^32=4G种可能出现的ip地址,每个ip地址出现的次数不确定,这个具体是由100G大文件决定的。对 每个小文件进行处理,我们知道前面每个文件中的ip是通过hash(ip)%1024。这样相当于将2^32=4G种ip地址进行了分段,每个文件中可能 出现的ip最大范围是4G/1024=4M。创建一个hashmap,读取小文件中的每个ip地址,判断hashmap中是否有这个ip,如果没有,这往 haspmap中插入一个的键值对,即hashmap.put(ip,1);如果haspmap中已经存在了这个ip,那么求出 这个ip所对应的值count=haspmap.get(ip),然后往修改这个ip所对应的value,使其数量增加1,即 hashmap.set(ip,count+1)。
  3. 当我们求出每个文件中出现次数最大的ip地址以后,我们在比较这1024个文件中的那个ip出现次数最大
伪代码 hash(IP)%N get many small files int max = 0;
String maxip = null; for each file
    Hashmap hashmap;
    String IP = readIP(file); if(hashmap.has(IP)) { int cnt = hashmap.get(IP);
        hashmap.set(IP, cnt+1); if(cnt+1 > max) { 
                 max = cnt+1;
                 maxip = IP;
        }
    } else hashmap.put(IP, 1);

阅读(649) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~