`

提取出某日访问网站次数最多的那K个IP

阅读更多

提取出某日访问百度次数最多的那K个IP

 

基本思路:ip最多2^32个,放入内存也要40G,基本不现实。所以只有用外排序,把ip分割成到不同的小文件里,然后统计次数后,汇总。另外,ip本质就是一32bit的数值,不要拘泥于字符串表示的ip。

思路也可参考此处问题一

基于以上思路,看代码:

 

package com.kingdee.gmis.mass.data.ips;

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Random;

import com.kingdee.gmis.common.TopNHeap;
import com.kingdee.gmis.mass.data.FileUtils;

/**
 * 提取出某日访问百度次数最多的那K个IP。<br>
 * 注意,此处简化起见,没有处理重复的情况,即有多个ip出现次数一样多
 * 
 * @author Administrator
 * 
 */
public class MassIP {
	public static int K10 = 1024 * 10;
	public static int M1 = 1024 * 1024;
	public static int M4 = 4 * M1;
	private static int partationCount = 100;

	/**
	 * @param args
	 * @throws IOException
	 */
	public static void main(String[] args) throws IOException {
		generateMassIp("ip", "ips.txt", 100000000);
		generatePartitionFile("ip", "ips.txt", 100);
		searchTopN(10);
		// searchTopN2("ip", "ips.txt", 10);
	}

	/**
	 * 如果是1亿条记录,直接放到内存排序会如何呢?
	 * 
	 * @param srcDirName
	 * @param srcFileName
	 * @param count
	 * @throws IOException
	 */
	public static void searchTopN2(String srcDirName, String srcFileName,
			int count) throws IOException {
		Map<Integer, Integer> ipCountMap = new HashMap<Integer, Integer>();
		File file = FileUtils.getFile(srcDirName, srcFileName);
		BufferedReader br = null;
		try {
			br = new BufferedReader(new FileReader(file), M4);
			String s;
			int i = 0, j = 0;
			while ((s = br.readLine()) != null) {
				int ip = parseIp2Int(s);
				Integer cnt = ipCountMap.get(ip);
				if (cnt == null) {
					i++;
					if (i % 10000000 == 0) {
						System.out.println(i);
					}
				}
				j++;
				if (j % 10000000 == 0) {
					System.out.println(j);
				}
				ipCountMap.put(ip, cnt == null ? 1 : cnt + 1);
			}
		} finally {
			if (br != null) {
				try {
					br.close();
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
		}
		TopNHeap<IPInfo> heap = new TopNHeap<IPInfo>(count);
		searchMostCountIps(ipCountMap, heap);
		printResult(heap);
	}

	/**
	 * 查找出现次数最多的K个ip地址
	 * 
	 * @param count
	 * @throws IOException
	 */
	public static void searchTopN(int count) throws IOException {
		File[] smallFiles = getPartitionFile("ip", partationCount);
		DataInputStream dis = null;
		Map<Integer, Integer> ipCountMap = new HashMap<Integer, Integer>();
		TopNHeap<IPInfo> heap = new TopNHeap<IPInfo>(count);
		for (int i = 0; i < partationCount; i++) {
			ipCountMap.clear();
			try {
				dis = new DataInputStream(new BufferedInputStream(
						new FileInputStream(smallFiles[i]), K10));
				while (dis.available() > 0) {
					int ip = dis.readInt();
					Integer cnt = ipCountMap.get(ip);
					ipCountMap.put(ip, cnt == null ? 1 : cnt + 1);
				}
				searchMostCountIps(ipCountMap, heap);
			} finally {
				if (dis != null) {
					try {
						dis.close();
					} catch (IOException e) {
						e.printStackTrace();
					}
				}
			}
		}
		printResult(heap);
	}

	/**
	 * 打印结果集
	 * 
	 * @param heap
	 */
	private static void printResult(TopNHeap<IPInfo> heap) {
		while (heap.hasNext()) {
			System.out.println(heap.removeTop().toString());
		}
	}

	/**
	 * 查找出现次数最多的ip
	 * 
	 * @param map
	 * @param heap
	 */
	private static void searchMostCountIps(Map<Integer, Integer> map,
			TopNHeap<IPInfo> heap) {
		Iterator<Integer> iter = map.keySet().iterator();
		Integer key = null;
		while (iter.hasNext()) {
			key = iter.next();
			int count = map.get(key);
			if (!heap.isFull() || count > heap.getHeapTop().getCount()) {
				heap.addToHeap(new IPInfo(count, key));
			}
		}
	}

	/**
	 * 把32位int值转换成ip字符串
	 * 
	 * @param value
	 * @return
	 */
	public static String parseInt2Ip(int value) {
		StringBuilder sb = new StringBuilder(15);
		String[] segs = new String[4];
		for (int i = 0; i < 4; i++) {
			segs[3 - i] = String.valueOf((0xFF & value));
			value >>= 8;
		}
		for (int i = 0; i < 4; i++) {
			sb.append(segs[i]).append(".");
		}
		sb.deleteCharAt(sb.length() - 1);
		return sb.toString();
	}

	/**
	 * 把ip字符串转换成int值
	 * 
	 * @param ip
	 * @return
	 */
	public static int parseIp2Int(String ip) {
		String[] segs = ip.split("\\.");
		int rst = 0;
		for (int i = 0; i < segs.length; i++) {
			rst = (rst << 8) | Integer.valueOf(segs[i]);
		}
		return rst;
	}

	/**
	 * 随机生成ip
	 * 
	 * @param srcDirName
	 * @param srcFileName
	 * @param count
	 * @throws IOException
	 */
	public static void generateMassIp(String srcDirName, String srcFileName,
			int count) throws IOException {
		File file = FileUtils.createFile(srcDirName, srcFileName);
		BufferedWriter bw = null;
		try {
			bw = new BufferedWriter(new FileWriter(file));
			count = count / 100;
			Random rd = new Random(255);
			StringBuilder sb = new StringBuilder(1500);
			for (int i = 0; i < count; i++) {
				sb.delete(0, sb.length());
				for (int j = 0; j < 100; j++) {
					sb.append(rd.nextInt(100)).append(".");
					sb.append(rd.nextInt(150)).append(".");
					sb.append(rd.nextInt(256)).append(".");
					sb.append(rd.nextInt(256)).append("\n");
				}
				bw.write(sb.toString());
				bw.flush();
			}
		} finally {
			if (bw != null) {
				bw.close();
			}
		}
	}

	public static File[] getPartitionFile(String srcDirName, int count)
			throws IOException {
		File[] files = new File[count];
		for (int i = 0; i < count; i++) {
			files[i] = FileUtils.getFile(srcDirName, i + ".data");
		}
		return files;
	}

	/**
	 * 分割大文件到小文件中
	 * 
	 * @param srcDirName
	 * @param srcFileName
	 * @param count
	 * @return
	 * @throws IOException
	 */
	public static File[] generatePartitionFile(String srcDirName,
			String srcFileName, int count) throws IOException {
		File[] files = new File[count];
		DataOutputStream[] dops = new DataOutputStream[count];
		for (int i = 0; i < count; i++) {
			files[i] = FileUtils.createFile(srcDirName, i + ".data");
		}
		File file = FileUtils.getFile(srcDirName, srcFileName);
		BufferedReader br = null;
		// Buffered
		try {
			for (int i = 0; i < count; i++) {
				dops[i] = new DataOutputStream(new BufferedOutputStream(
						new FileOutputStream(files[i]), K10));
			}
			br = new BufferedReader(new FileReader(file), M4);
			String s;
			while ((s = br.readLine()) != null) {
				int ip = parseIp2Int(s);
				dops[Math.abs(ip % count)].writeInt(ip);
			}
		} finally {
			for (int i = 0; i < count; i++) {
				if (dops[i] != null) {
					try {
						dops[i].close();
					} catch (IOException e) {
						e.printStackTrace();
					}
				}
			}
			if (br != null) {
				try {
					br.close();
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
		}
		return files;
	}

	/**
	 * 表示IP信息,存有次数和ip值。在放入堆中时候会用作存储
	 * 
	 * @author Administrator
	 * 
	 */
	static class IPInfo implements Comparable<IPInfo> {
		private int count;
		private int ipValue;

		public IPInfo(int count, int ipValue) {
			super();
			this.count = count;
			this.ipValue = ipValue;
		}

		public int getCount() {
			return count;
		}

		public void setCount(int count) {
			this.count = count;
		}

		public int getIpValue() {
			return ipValue;
		}

		public void setIpValue(int ipValue) {
			this.ipValue = ipValue;
		}

		public String getIp() {
			return parseInt2Ip(ipValue);
		}

		@Override
		public int compareTo(IPInfo o) {
			if (this.count > o.getCount()) {
				return 1;
			} else if (this.count < o.getCount()) {
				return -1;
			} else {
				return 0;
			}
		}

		public String toString() {
			return this.getIp() + " -- " + this.count;
		}

	}
}

以上代码用到了前边文章中提到的top K堆

此方法,内存占用情况也非常理想,高峰不到100m内存就搞定了。

扩展:

 如果我们是排序1亿条ip,算下是1*4/10 = 0.4G,那么说400+m的内存也够把所有的1亿条ip的统计都放入到内存当中了?上边代码中searchTopN2是这么做了下,但是情况很不理想,读入2kw条记录的时候,内存已经占用到了快1G:

这是什么原因呢?虽然是java对象,但是分析下,HashMap的key和value都是Integer,从下图Integer的非静态变量和非静态方法看,直观分析也就value这个field占用一个字节嘛,两个Integer顶多也就是占用800+m的内存嘛,为何会1g才读入2kw整数呢?

这个问题,且等我们继续深究!

另,本题目的多线程版本后续贴出

 

  • src.rar (8.3 KB)
  • 下载次数: 14
分享到:
评论

相关推荐

    面试 大数据 算法解析

    1.提取出某日访问百度次数最多的那个IP 2.有一个1G大小的一个文件,里面每一行是一个词 3.给定a、b两个文件,各存放50亿个url,每个url各占64字节,内存限制是4G,让你找出a、b文件共同的url? 4.在2.5亿个整数中找出...

    java排序算法使用及场景说明

    在这个场景中,我们有海量日志数据,问题是如何提取出某日访问百度次数最多的那个 IP? 解决方案 1:首先是这一天,并且是访问百度的日志中的 IP 取出来,逐个写入到一个大文件中,然后采用映射的方法,找出每个小...

    大数据常见算法题.txt

    第一部分、十道海量数据处理面试题 1、海量日志数据,提取出某日访问百度次数最多的那个IP。 此题,在我之前的一篇文章算法里头有所提到,当时给出的方案是:IP的数目还是有限的,最多2^32个,所以可以考虑使用hash...

    大数据面试题目

    大数据面试题目的解决方法可以应用于实际的数据处理中,例如,在海量日志数据中,使用Bloom filter可以快速判断某个元素是否存在于一个集合中,而使用Hashing可以快速提取出某日访问百度次数最多的那个IP。...

    10道海量数据处理题目.pdf

    1. 提取出某日访问百度次数最多的IP 这是一个典型的分布式计算问题。首先,通过对IP地址取模将海量日志分散到多个小文件中,例如模1000,生成1000个小文件。然后,对每个小文件使用哈希映射(如hash_map)统计IP地址...

    十道海量数据处理面试题与十个方法大总结

    一、海量日志数据,提取出某日访问百度次数最多的那个 IP 这是一个典型的 hash 表应用问题,解决方案是使用 hash 表将 IP 直接存入内存,然后进行统计。在实际操作中,可以将大文件映射为多个小文件,然后找出每个...

    SQL数据库对于海量数据面试题及答案.pdf

    海量日志数据,提取出某日访问百度次数最多的那个IP。 方案 1:首先是这一天,并且是访问百度的日志中的IP 取出来,逐个写入到一个大文件中。注意到 IP 是 32 位的,最多有个IP。同样可以采用映射的方法,比如模...

    java八股文整理,非常全面可靠

    对于海量日志数据,例如需要提取出某日访问百度次数最多的那个IP,可以使用映射的方法,即%1000将整个大文件映射为1000个小文件,然后逐个写入到一个大文件中,然后对每个小文件中的所有IP进行频率统计,最后在这...

    各大单位的面试题

    提取出某日访问百度次数最多的IP #### 题目描述 从海量日志数据中,找出某天访问百度次数最多的IP地址。 #### 解答思路 - 使用哈希策略将日志数据分布到多个小文件中,例如通过IP地址的哈希值对1024取模,得到...

    十道海量数据处理面试题(卷).doc

    1. 提取出某日访问百度次数最多的 IP: 这题通常需要使用流式处理,如 MapReduce 或者 Hadoop。可以先通过 Map 阶段对每个 IP 进行计数,然后在 Reduce 阶段汇总并找出最大值。 2. 找出频数最高的 100 个词: ...

    数据挖掘的一些题目

    4. 海量日志数据分析:有海量日志数据,要求提取出某日访问百度次数最多的那个 IP。解决方案是首先提取出这一天的日志中的 IP,然后使用映射的方法将其分割为 1000 个小文件,最后找出每个小文件中出现频率最大的 IP...

    常用大数据量,海量数据处理方法,算法总结

    2. 海量日志数据,提取出某日访问百度次数最多的那个 IP。 3. 如何根据输入元素个数 n,确定位数组 m 的大小及哈希函数个数 k。 这些问题可以使用上述方法来解决,例如使用 Bloom filter 或 Hashing 等方法来查找、...

    十道海量数据处理面试题与十个方法大总结 面试必备

    提取某日访问百度次数最多的那个IP** **问题描述**:给定一天内的大量日志数据,需要从中提取出访问百度次数最多的那个IP。 **解决方案**:考虑到IP地址的数量有限,最多2^32个,可以考虑使用哈希表(如`hash_map...

    大数据量,海量数据处理

    4. 给定海量日志数据,需要提取出某日访问百度次数最多的那个IP。解决方法是使用HashMap来统计每个IP的访问次数,然后使用堆排序来输出访问次数最多的IP。 5. 给定2.5亿个整数,需要找出不重复的整数,内存空间不...

    海量数据处理:十道面试题与十个海量数据处理方法总结

    **1、海量日志数据,提取出某日访问百度次数最多的那个IP** - **问题概述**: 给定一天内的海量日志数据,从中找出访问百度次数最多的IP地址。 - **解决方案**: - **初步思路**: 将所有IP地址写入一个大文件,考虑...

    面试中的大数据处理

    问题实例:海量日志数据,提取出某日访问百度次数最多的那个IP。IP的数目还是有限的,最多2^32个,所以可以考虑使用hash将ip直接存入内存,然后进行统计。 3.bit-map: Bit-map是一种常见的大数据处理方法,适用...

    程序员大厂面试百度篇.pdf

    * 海量日志数据,提取出某日访问百度次数最多的那个IP(大数据处理) * 有10个文件,每个文件1G,每个文件的每一行都存放的是用户的query,每个文件的query都可能重复。如何按照query的频度排序?(大数据处理) ...

Global site tag (gtag.js) - Google Analytics