首页 > 试题广场 >

假设我们通过对凤凰新闻日志的清理获取到一亿条新闻的URL地址

[问答题]

假设我们通过对凤凰新闻日志的清理获取到一亿条新闻的URL地址，现在需要统计出一亿条新闻URL中最热门的五十条新闻URL（这些新闻URL重复度比较高，虽然总数是一亿，如果去重之后，大约有三千万条新闻URL,URL去重过程不需要考虑，一条新闻URL的重复度越高，说明阅读该新闻的用户越多，也就是越热门，每条新闻URL长度限制不超过255字节），要求使用的内存不超过8G，请写出基本思路与步骤。（该题不计入试卷得分，有时间则完成）

cyanlong

首先用HashMap表映射出每条URL对应的重复值，key为URL，值为重复值。

//伪代码
String url;
HashMap<String, Integer> map = new HashMap<String, Integer>();
while (fileStream.hasNext()){
    url = read();
   if (map.containsKey(url)){
        map.get(url)++;
    }else{
        map.put(url, 1);
    }
}

之后，我们使用长度为50的最小堆来找到最热的50条数据。就是一个top-k问题。

PriorityQueue<Map.Entry<String, Integer>> queue = 
	new PriorityQueue<Map.Entry<String, Integer>>(50, 
           new Comparator<Map.Entry<String, Integer>>(){
	        @Override public int compare(Entry<String, Integer> o1, Entry<String, Integer> o2) {
	    	    return o1.getValue() - o2.getValue();
                }
	    });
		
int k = 50;
for (Map.Entry<String, Integer> entry : map.entrySet()){
    if (queue.size() < k){
        queue.add(entry);
    } else {
        if (entry.getValue() > queue.peek().getValue()){
            queue.poll();
	    queue.add(entry);
        }
    }
}

ok，我们最后来算一算是否满足8G内存的要求。

这里，内存耗用最大的时候为有三千万条数据的hash表，三千万条url大小为：30, 000, 000 * 255 byte = 7.124G，3000万个int值为：30,000,000 * 4 = 0.118G。

当我们使用PriorityQueue过滤数据时，可以将以过滤掉的HashMap中的值remove掉。

这样，内存耗用最大时大约为：7.12G + 0.11G < 8G。基本满足题目。

我们在来分析分析时间复杂度吧，第一步统计重复次数的时间复杂度为O(n)，第二部用PriorityQueue过滤时时间复杂度为O(mlgK)，这里，n为原始数据量即1亿，m为去重后的三千万，k为二叉堆的长度50。

编辑于 2017-01-23 20:00:46 回复(0)