题目:每一个ip访问百度,其ip地址都会被记录到后台日志文件中,假设一天的访问日志有100G,求出一天中访问百度次数最多的ip地址,可以使用的内存大小是1G。
分析
-
首先解决大文件问题,也就是如何处理100G的一个大文件,这个通常的解决方法就是将大文件分解成许多小文件。我们可以通过对IP地址求hash然后对1024取模将一个100G的大文件分解成1024个小文件(file0,file1......file1023),注意这里的1024个文件并不是平均分的,也就是每个文件大小并不是(100G/1204)。当然我们考虑的时候可以假设文件是平均分的,那么每个文件大小为100M,这样一个100M的文件是可以全部读入大小为1G内存中。这样就解决了第一个文件太大不能一次读入内存的问题。
-
考虑到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)。
-
当我们求出每个文件中出现次数最大的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);
阅读(651) | 评论(0) | 转发(0) |