看了教你如何迅速秒杀掉:99%的海量数据处理面试题一文,的确是挺有收获的,特别是对这种海量数据的处理,的确是有了一个挺清晰的思路,特别感谢原文博主July。
处理海量数据问题存在的原因就在于1)数据量太大,无法在短时间内解决;2)内存不够,没办法装下那么多的数据。
而对应的办法其实也就是分成1)针对时间,合适的算法+合适的数据结构来提高处理效率;2)针对空间,就是分而治之,将大数据量拆分成多个比较小的数据片,然后对其各个数据片进行处理,最后再处理各个数据片的结果。
原文中也给出一个问题,“从1亿个ip中访问次数最多的IP”,就试着来解决一下吧。
1)首先,生成1亿条数据,为了产生更多的重复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大概是15Btye,所以生成的ip文件,大概是1,500,000,000Byte = 1,500,000 KB,如下:
2)文件生成了,那么我们现在就要假设内存不是很够,没有办法一次性装入那么多的数据,所以要先把文件给拆分成多个小文件。
在这里采取的是就是Hash取模的方式,将字符串的ip地址给转换成一个长整数,并将这个数对1000取模,将模一样的ip放到同一个文件,这样就能够生成1000个小文件,每个文件就只有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 = 1000;
下面是拆文件的函数:
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映射之后,就直接打开文件,将其加到对应的文件末尾,那么有1亿条ip,我们就要读写文件1亿次,那IO开销的时候就相当大,所以我们可以先拿一个Map放着,等到一定的规模之后,再统一写进文件,然后把map清空,继续映射,这样的话,就能够提高折分的速度。而这个规模,就是根据能处理的内存来取的值的,如果内存够大,这个值就可以设置大点,如果内存小,就要设置小一点的值,IO开销跟内存大小,总是需要在这两者之间的取个平衡点的。
可以看到,这样我们拆分成了1000个小文件,每个文件只有1500KB左右,所耗的时间如下,7分钟到8分钟左右:
Start Divide Ips File: 06:18:11.103
End: 06:25:44.134
而这种映射可以保证同样的IP会映射到相同的文件中,这样后面在统计IP的时候,就可以保证在a文件中不是最多次数的ip(即使是第2多),也不会出现在其它的文件中。
3)文件拆分了之后,接下来我们就要分别读取这1000个小文件,统计其中每个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)当1000个文件都读取完之后,我们就会产生一个有1000条记录的map,里面存储了每个文件中访问次数最多的ip,我们再调用count()方法,找出这个map中访问次数最大的ip,即这1000个文件中,哪个文件中的最高访问量的IP,才是真正最高的,好像小组赛到决赛一样。。。。
3.3)在这里没有用到什么堆排序和快速排序,因为只需要一个最大值,所以只要拿当前的最大值跟接下来的值判断就好,其实也相当跟只有一个元素的堆的堆顶元素比较。
下面就是我们的结果 。
Start Calculate Ips: 06:37:51.088
result IP : 192.168.67.98 | count = 1707
End: 06:44:30.229
到这里,我们就把这个ip给查找出来了。
其实理解了这个思路,其它的海量数据问题,虽然可能各个问题有各个问题的特殊之处,但总的思路我觉得应该是相似的。
分享到:
相关推荐
【输入形式】 从标准输入读取输入。第一行只有一个数字N(1≤N≤10000),代表整数的个数。以后的N行每行有一个整数。 【输出形式】 向标准输出打印出现次数...输入6个整数,其中出现次数最多的是0,共出现两次。
实现2-1众数问题.cpp
原理:创建一个新的空字典,用循环的方式来获取列表中的每一个元素,判断获取的元素是否存在字典中的key,如果不存在的话,将元素作为key,值为列表中元素的count # 字典方法 words = [ 'my', 'skills', 'are', '...
设a 和b是2 个正整数,a≤b,找出a 和b之间约数个数最多的数x。 算法设计: 对于给定的2 个正整数a 计算a 和b之间约数个数最多的数。 可以保证a和b都不超过2000000. 数据输入: 输入数据有2个正整数a和b。 结果...
# 返回一个列表中出现次数最多的元素 def showmax(lt): index1 = 0 #记录出现次数最多的元素下标 max = 0 #记录最大的元素出现次数 for i in range(len(lt)): flag = 0 #记录每一个元素出现的次数 for ...
Hadoop按日期统计访问次数代码实现,以及包含测试用的数据
本文实例讲述了JS获取数组中出现次数最多及第二多元素的方法。分享给大家供大家参考,具体如下: 整型数组中出现次数最多和第二多的元素 用哈希数组 function f(arr){ var i; var length=arr.length; var hash=...
本文实例讲述了Python实现计算字符串中出现次数最多的字符。分享给大家供大家参考,具体如下: 1. 看了网上挺多写的方法都没达到我所需要的效果,我干脆自己写了个方法共享给大家 ee = 'aa111(((bbhhhhhh%jjjjjj%...
先从标准输入读入整数的个数(大于等于1,小于等于100),然后在下一行输入这些整数,各整数之间以一个空格分隔。 【输出形式】 在标准输出上输出出现次数最多的整数及其出现次数,两者以一个空格分隔;若出现次数...
我们在一些统计工作或者分析过程中,有事会遇到要统计一个序列中出现最多次的元素,比如一段英文中,查询出现最多的词是什么,及每个词出现的次数。一遍的做法为,将每个此作为key,出现一次,value增加1。 例如: ...
主要介绍了Springboot过滤器禁止ip频繁访问功能实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
1.提取出某日访问百度次数最多的那个IP 2.有一个1G大小的一个文件,里面每一行是一个词 3.给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url? 4.在2.5亿个整数中找出...
Jsoup实现省市区的爬取,突破ip的访问限制,实现动态ip代理,爬取最新的省市区信息
在一个由元素组成的表中,出现次数最多的元素成为众数。试写一个寻找中枢的算法,并分析其计算复杂性。 输出众数和该众数的重数。 算法流程: 1、 用快速排序算法QuickSort()先将数组排序; 2、 用数组b[]存储每个...
第一部分、十道海量数据处理面试题 1、海量日志数据,提取出某日访问百度次数最多的那个IP。 此题,在我之前的一篇文章算法里头有所提到,当时给出的方案是:IP的数目还是有限的,最多2^32个,所以可以考虑使用hash...
一个简单的使用hash来实现从海量IP地址中查询是否存在待查找的IP地址。主要特点有: (1)使用批处理,一键自动编译,处理;可直接运行。 (2)完美的展示了hash在查询中的使用方法。
在这个解决方案中,我们将讨论如何让内网用户通过域名或公网IP访问内部服务器。这个解决方案可以分为两部分,一部分是内网用户和内部服务器不在同一个网段,另一部分是内网用户和内部服务器在同一个网段。 内网用户...
1. 给定a、b两个文件,各存放50亿个url,每个url...4. 海量日志数据,提取出某日访问百度次数最多的那个IP。(利用hash分而治之,然后上归并,堆) 5. 在2.5亿个整数中找出不重复的整数,内存不足以容纳这2.5亿个整数。
java ip匹配 访问量+1 从 `IP地址文件` 中读取地址关系到自己的数据结构中; 2. 从 `日志文件` 中读取ip,解析关联的城市,对应的城市访问量 `+1` ; 3. 统计访问量最多的前10城市
公元1年1月1日为星期一给定字符串,找出出现次数最多的字符,并且计算次数。给定字符串,找出出现次数最多的字符,并且计算次数。编程:编写一个截取字符串的函数,输入为一个字符串和字节数,输出为按字节截取的...