700字范文 > 关于某日访问次数最多的IP的topK问题的三种解法

关于某日访问次数最多的IP的topK问题的三种解法

时间：2019-11-13 07:10:57

题目描述

在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()

结果如下：