题目描述
在july大神的博客中,看到这样两道题:
1. 海量日志数据,提取出某日访问百度次数最多的那个IP。2. 假设目前有一千万个记录(这些查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多,也就是越热门。),请你统计最热门的10个查询串,要求使用的内存不能超过1G。
现在我将两题结合一下:
假如有1千万+的ip,如何知道访问次数最多的topk ip呢?假设k为10
来源:/v_JULY_v/article/details/6256463
生成1千万的IP
我们来生成1千万+的ip
# coding:utf-8# /bin/pythondef generateRandom(rangeFrom, rangeTo):import randomreturn random.randint(rangeFrom,rangeTo)def generageMassiveIPAddr(fileLocation,numberOfLines):IP = []file_handler = open(fileLocation, 'a+')for i in range(numberOfLines):IP.append('10.197.' + str(generateRandom(0,255))+'.'+ str(generateRandom(0,255)) + '\n')file_handler.writelines(IP)file_handler.close()if __name__ == '__main__':from time import ctimeprint ctime()for i in range(10):print ' ' + str(i) + ": " + ctime()generageMassiveIPAddr('imassiveIP.txt', 1000000)print ctime()
通过这段代码我们可以在当前的目录生成一个10010000行的imassiveIP.txt文件
$ wc -l imassiveIP.txt 10010000 imassiveIP.txt
我将这个文件作为我们的数据来进行实验
解法1 通过linux shell来计算,实现最快
$ time cat imassiveIP.txt | sort | uniq -c | sort -nrk1 | head -n 10204 10.197.30.171202 10.197.92.207202 10.197.42.72201 10.197.195.77201 10.197.190.108200 10.197.49.128200 10.197.236.54200 10.197.223.59200 10.197.145.27199 10.197.43.98real 1m18.731suser 1m17.010ssys0m1.090s
可以看到我们花费时间为1m18.731s
综合分析一下,第一步排序的时间复杂度是O(NlgN)
,而uniq
遍历的时间复杂度是O(N)
,假设去重后的数为M个,则第二步排序的时间复杂度为O(MlgM)
因此该算法的总体时间复杂度就是O(N+NlgN+MlgM)=O(NlgN)
解法2 Hash Table法+部分排序
第一步:维护一个Key为IP字串,Value为该IP出现次数的HashTable,每次读取一个IP,如果该字串不在Table中,那么加入该字串,并且将Value值设为1;如果该字串在Table中,那么将该字串的计数加一即可。最终我们在O(N)的时间复杂度内完成了对该海量数据的处理。第二步题目要求是求出Top 10,因此我们没有必要对所有的IP都进行排序,我们只需要维护一个10个大小的数组,初始化放入10个IP,按照每个IP的统计次数由大到小排序,排序的时间复杂度为O(klg(k))
, 假设去重后的数为M个, 然后遍历这M条记录,每读一条记录就和数组最后一个IP对比,如果小于这个IP,那么继续遍历,否则,将数组中最后一条数据淘汰,加入当前的IP。最后当所有的数据都遍历完毕之后,那么这个数组中的10个IP便是我们要找的Top10了。
python 代码实现
#coding:utf-8#/bin/pythonimport sys, osfrom collections import defaultdictdef main():if len(sys.argv) != 2:print "Usage: python **.py topK"sys.exit(1)else:#print sys.argvk = int(sys.argv[1])res_dict = defaultdict(int)topk_dict = defaultdict(int)for line in sys.stdin:res_dict[line.strip()] += 1topk_dict_sorted = []for key, value in res_dict.items():if len(topk_dict) <= k:topk_dict[key] = valueif len(topk_dict) == k:topk_dict_sorted = sorted(topk_dict.items(), key=lambda x:x[1], reverse=True)else:if topk_dict_sorted[-1][1] < value:topk_dict_sorted.pop()topk_dict_sorted.append((key, value))topk_dict_sorted = sorted(topk_dict_sorted, key=lambda x:x[1], reverse=True)if len(topk_dict_sorted) < k:topk_dict_sorted = sorted(topk_dict.items(), key=lambda x:x[1], reverse=True)for key, value in topk_dict_sorted:print "%s\t%d"%(key, value)if __name__ == '__main__':main()
结果如下
$ time cat imassiveIP.txt| python get_top10.py 10 10.197.30.171 20410.197.92.207 0.197.42.72 0.197.190.108 0.197.195.77 0.197.236.54 20010.197.145.27 20010.197.49.128 20010.197.223.59 20010.197.241.183 199real 0m5.046suser 0m4.730ssys0m0.290s
我们发现我们只需要用5.046s
就可以找到这个top10的ip
综合分析一下,第一步统计频数时间复杂度是O(N)
,假设去重后的数为M个,则第二步计算的时间复杂度为O(M*k*lgk)
, 其中O(k*lgk)
为对k个数排序的时间复杂度,因此该算法的总体时间复杂度就是O(N+M*k*lgk)
,这个速度比直接shell已经快了10几倍了。
方法3 Hash Table法+堆
我们主要做的优化是如何在去重后的M个IP中找到topK个最大的,在方法二中,我们采取的是先排序然后插入到最后位置排序, 其实也可以通过采用二分的方法查找,应该插入的合适位置,这样就可以避免再排序,这样操作的复杂度就降到了logK,可是,随之而来的问题就是数据移动,因为移动数据次数增多了。有没有既能快速查找,又能快速移动元素的数据结构呢?回答是肯定的,那就是堆。
借助堆结构,我们可以在log量级的时间内查找和调整/移动。因此到这里,我们的算法可以改进为这样,维护一个K(该题目中是10)大小的小根堆,然后遍历M个IP,分别将出现次数和根元素进行对比。
具体过程是:
堆顶存放的是整个堆中最小的数,现在遍历N个数,把最先遍历到的k个数存放到最小堆中,并假设它们就是我们要找的最大的k个数,X1>X2...XminX1>X2...Xmin(堆顶),而后遍历后续的N-K个数,一一与堆顶元素进行比较,如果遍历到的XiXi大于堆顶元素XminXmin,则把Xi放入堆中,而后更新整个堆,更新的时间复杂度为O(lgK)
,如果Xi<XminXi<Xmin则不更新堆,整个过程的复杂度为O(K)+O((M-K)*logK)=O(M*logK)
这个有个关于堆排序很好3d动画链接
python 实现1
一个速度还可以但是空间复杂度很高的程序,在python中有个heapq
可以直接实现堆.关于heap
的详细用法可以看这里
我们把所有的数据都都放在堆中,然后直接返回最大的k个数据就可以了,时间复杂度是Time complexity: O(M + klogM)
,总的时间复杂度为O(N+M+klgM)
#coding:utf-8#/bin/pythonimport sys, osfrom collections import defaultdictimport heapqdef main():if len(sys.argv) != 2:print "Usage: python **.py topK"sys.exit(1)else:#print sys.argvk = int(sys.argv[1])res_dict = defaultdict(int)heap_res = []for line in sys.stdin:res_dict[line.strip()] += 1for key, value in res_dict.items():heap_res.append((value, key))heap_res = heapq.nlargest(k, heap_res)for key, value in heap_res:print "%s\t%d"%(value, key)if __name__ == '__main__':main()
结果如下:
$ time cat imassiveIP.txt | python get_top10_heap.py 10 10.197.30.171 20410.197.92.207 0.197.42.72 0.197.195.77 0.197.190.108 0.197.49.128 20010.197.236.54 20010.197.223.59 20010.197.145.27 20010.197.43.98 199real 0m5.085suser 0m4.760ssys0m0.300s
python实现2
如果不排序输出Time Complexity: O(k + (M-k)Logk)
,如果排序输出Time Complexity:O(k + (M-k)Logk + kLogk)=O(k + MLogk)
,所以总的Time Complexity:O(N + k + MLogk)
#coding:utf-8#/bin/pythonimport sys, osfrom collections import defaultdictimport heapqdef main():if len(sys.argv) != 2:print "Usage: python **.py topK"sys.exit(1)else:k = int(sys.argv[1])res_dict = defaultdict(int)heap_res = []for line in sys.stdin:res_dict[line.strip()] += 1for key, value in res_dict.items():if len(heap_res) < k:heap_res.append((value, key))if len(heap_res) == k:heapq.heapify(heap_res)else:if value > heap_res[0][0]:heapq.heappushpop(heap_res, (value, key))heap_res = heapq.nlargest(k, heap_res)for key, value in heap_res:print "%s\t%d"%(value, key)if __name__ == '__main__':main()
结果如下:
$ time cat imassiveIP.txt | python get_top10_heap.py 10 10.197.30.171 20410.197.92.207 0.197.42.72 0.197.195.77 0.197.190.108 0.197.49.128 20010.197.236.54 20010.197.223.59 20010.197.145.27 20010.197.43.98 199real 0m4.917suser 0m4.670ssys0m0.220s
总结
如果我们处理大批量的数据时候,还是要学会优化代码,但是掌握shell
的命令行使用方法,可以极大的提高我们的效率
参考链接
十一、从头到尾解析Hash表算法
【原创】Python处理海量数据的实战研究
/k-largestor-smallest-elements-in-an-array/