BAT面试上机题从3亿个ip中找出访问次数最多的IP…
2018-06-29 06:17:31来源：博客园 阅读 ()
我们面临的问题有以下两点：
1）数据量太大，无法在短时间内解决；
2）内存不够，没办法装下那么多的数据。
而对应的办法其实也就是分成1）针对时间，合适的算法+合适的数据结构来提高处理效率；2）针对空间，就是分而治之，将大数据量拆分成多个比较小的数据片，然后对其各个数据片进行处理，最后再处理各个数据片的结果。
原文中也给出一个问题，"从3亿个ip中访问次数最多的IP"，就试着来解决一下吧。
1）首先，生成3亿条数据，为了产生更多的重复ip，前面两节就不变了，只随机生成后面的2节。
private static String generateIp() {
return "192.168." + (int) (Math.random() * 255) + "."
+ (int) (Math.random() * 255) + "\n";
}
private static void generateIpsFile() {
File file = new File(FILE_NAME);
try {
FileWriter fileWriter = new FileWriter(file);
for (int i = 0; i < MAX_NUM; i++) {
fileWriter.write(generateIp());
}
fileWriter.close();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
1个char是一个Byte，每个ip大概是11Btye，所以生成的ip文件，大概是3,500,000 KB，如下：
2）文件生成了，那么我们现在就要假设内存不是很够，没有办法一次性装入那么多的数据，所以要先把文件给拆分成多个小文件。
在这里采取的是就是Hash取模的方式，将字符串的ip地址给转换成一个长整数，并将这个数对3000取模，将模一样的ip放到同一个文件，这样就能够生成3000个小文件，每个文件就只有1M多，在这里已经是足够小的了。
首先是hash跟取模函数：
private static String hash(String ip) {
long numIp = ipToLong(ip);
return String.valueOf(numIp % HASH_NUM);
}
private static long ipToLong(String strIp) {
long[] ip = new long[4];
int position1 = strIp.indexOf(".");
int position2 = strIp.indexOf(".", position1 + 1);
int position3 = strIp.indexOf(".", position2 + 1);
ip[0] = Long.parseLong(strIp.substring(0, position1));
ip[1] = Long.parseLong(strIp.substring(position1 + 1, position2));
ip[2] = Long.parseLong(strIp.substring(position2 + 1, position3));
ip[3] = Long.parseLong(strIp.substring(position3 + 1));
return (ip[0] << 24) + (ip[1] << 16) + (ip[2] << 8) + ip[3];
}
2.1）将字符串的ip转换成长整数
2.2）对HASH_NUM，这里HASH_NUM = 3000；
下面是拆文件的函数：
private static void divideIpsFile() {
File file = new File(FILE_NAME);
Map<String, StringBuilder> map = new HashMap<String,StringBuilder>();
int count = 0;
try {
FileReader fileReader = new FileReader(file);
BufferedReader br = new BufferedReader(fileReader);
String ip;
while ((ip = br.readLine()) != null) {
String hashIp = hash(ip);
if(map.containsKey(hashIp)){
StringBuilder sb = (StringBuilder)map.get(hashIp);
sb.append(ip).append("\n");
map.put(hashIp, sb);
}else{
StringBuilder sb = new StringBuilder(ip);
sb.append("\n");
map.put(hashIp, sb);
}
count++;
if(count == 4000000){
Iterator<String> it = map.keySet().iterator();
while(it.hasNext()){
String fileName = it.next();
File ipFile = new File(FOLDER + "/" + fileName + ".txt");
FileWriter fileWriter = new FileWriter(ipFile, true);
StringBuilder sb = map.get(fileName);
fileWriter.write(sb.toString());;
fileWriter.close();
}
count = 0;
map.clear();
}
}
br.close();
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
2.3）在这里，我们如果每读取一个ip，经过hash映射之后，就直接打开文件，将其加到对应的文件末尾，那么有3亿条ip，我们就要读写文件3亿次，那IO开销的时候就相当大，所以我们可以先拿一个Map放着，等到一定的规模之后，再统一写进文件，然后把map清空，继续映射，这样的话，就能够提高折分的速度。而这个规模，就是根据能处理的内存来取的值的，如果内存够大，这个值就可以设置大点，如果内存小，就要设置小一点的值，IO开销跟内存大小，总是需要在这两者之间的取个平衡点的。
可以看到，这样我们拆分成了3000个小文件，每个文件只有1100KB左右，所耗的时间如下，17分钟到18分钟左右：
Start Divide Ips File: 06:18:11.103 End: 06:25:44.134
而这种映射可以保证同样的IP会映射到相同的文件中，这样后面在统计IP的时候，就可以保证在a文件中不是最多次数的ip（即使是第2多），也不会出现在其它的文件中。
3）文件拆分了之后，接下来我们就要分别读取这3000个小文件，统计其中每个IP出现的次数。
private static void calculate() {
File folder = new File(FOLDER);
File[] files = folder.listFiles();
FileReader fileReader;
BufferedReader br;
for (File file : files) {
try {
fileReader = new FileReader(file);
br = new BufferedReader(fileReader);
String ip;
Map<String, Integer> tmpMap = new HashMap<String, Integer>();
while ((ip = br.readLine()) != null) {
if (tmpMap.containsKey(ip)) {
int count = tmpMap.get(ip);
tmpMap.put(ip, count + 1);
} else {
tmpMap.put(ip, 0);
}
}
fileReader.close();
br.close();
count(tmpMap,map);
tmpMap.clear();
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
count(map,finalMap);
Iterator<String> it = finalMap.keySet().iterator();
while(it.hasNext()){
String ip = it.next();
System.out.println("result IP : " + ip + " | count = " + finalMap.get(ip));
}
}
private static void count(Map<String, Integer> pMap, Map<String, Integer> resultMap) {
Iterator<Entry<String, Integer>> it = pMap.entrySet().iterator();
int max = 0;
String resultIp = "";
while (it.hasNext()) {
Entry<String, Integer> entry = (Entry<String, Integer>) it.next();
if (entry.getValue() > max) {
max = entry.getValue();
resultIp = entry.getKey();
}
}
resultMap.put(resultIp,max);
}
3.1）第一步要读取每个文件，将其中的ip放到一个Map中，然后调用count()方法，找出map中最大访问次数的ip，将ip和最多访问次数存到另外一个map中。
3.2）当3000个文件都读取完之后，我们就会产生一个有3000条记录的map，里面存储了每个文件中访问次数最多的ip，我们再调用count()方法，找出这个map中访问次数最大的ip，即这3000个文件中，哪个文件中的最高访问量的IP，才是真正最高的，好像小组赛到决赛一样。。。。
3.3）在这里没有用到什么堆排序和快速排序，因为只需要一个最大值，所以只要拿当前的最大值跟接下来的值判断就好，其实也相当跟只有一个元素的堆的堆顶元素比较。
下面就是我们的结果 。
Start Calculate Ips: 06:37:51.088 result IP : 192.168.67.98 | count = 1707 End: 06:54:30.221
到这里，我们就把这个ip给查找出来了。
其实理解了这个思路，其它的海量数据问题，虽然可能各个问题有各个问题的特殊之处，但总的思路我觉得应该是相似的。
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有
上一篇：1.计算机发展阶段
下一篇：SpringMVC入门
- 2020年深圳中国平安各部门Java中级面试真题合集（附答案） 2020-06-11
- MyBatis中的$和#，用不好，准备走人！ 2020-06-11
- JVM常见面试题解析 2020-06-11
- SpringBoot 2.3 整合最新版 ShardingJdbc + Druid + MyBatis 2020-06-11
- 作为一个面试官，我想问问你Redis分布式锁怎么搞？ 2020-06-10
IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash
