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

梦里梦外; 2022-05-16 09:49 148阅读 0赞

# 题目描述 #

在july大神的博客中，看到这样两道题：

1. 海量日志数据，提取出某日访问百度次数最多的那个IP。
    2. 假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10个查询串，要求使用的内存不能超过1G。

现在我将两题结合一下：

假如有1千万+的ip,如何知道访问次数最多的topk ip呢？假设k为10

来源：[https://blog.csdn.net/v\_JULY\_v/article/details/6256463][https_blog.csdn.net_v_JULY_v_article_details_6256463]

# 生成1千万的IP #

我们来生成1千万+的ip

# coding:utf-8
    # /bin/python
    
    def generateRandom(rangeFrom, rangeTo):
        import random
        return 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 ctime
        print 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 10
        204 10.197.30.171
        202 10.197.92.207
        202 10.197.42.72
        201 10.197.195.77
        201 10.197.190.108
        200 10.197.49.128
        200 10.197.236.54
        200 10.197.223.59
        200 10.197.145.27
        199 10.197.43.98
    
    real    1m18.731s
    user    1m17.010s
    sys     0m1.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/python
    
    import sys, os
    from collections import defaultdict
    
    def main():
        if len(sys.argv) != 2:
            print "Usage: python **.py topK"
            sys.exit(1)
        else:
            #print sys.argv
            k = int(sys.argv[1])
        res_dict = defaultdict(int)
        topk_dict = defaultdict(int)
        for line in sys.stdin:
            res_dict[line.strip()] += 1
        topk_dict_sorted = []
        for key, value in res_dict.items():
            if len(topk_dict) <= k:
                topk_dict[key] = value
                if 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   204
    10.197.92.207   202
    10.197.42.72    202
    10.197.190.108  201
    10.197.195.77   201
    10.197.236.54   200
    10.197.145.27   200
    10.197.49.128   200
    10.197.223.59   200
    10.197.241.183  199
    
    real    0m5.046s
    user    0m4.730s
    sys     0m0.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...Xmin  X 1 > X 2 . . . X m i n (堆顶)，而后遍历后续的N-K个数，一一与堆顶元素进行比较，如果遍历到的Xi  X i 大于堆顶元素Xmin  X m i n ，则把Xi放入堆中，而后更新整个堆，更新的时间复杂度为`O(lgK)`，如果Xi<Xmin  X i < X m i n 则不更新堆，整个过程的复杂度为`O(K)+O(（M-K）*logK)=O（M*logK）`*

这个有个关于堆排序很好3d动画[链接][Link 1]

## python 实现1 ##

一个速度还可以但是空间复杂度很高的程序，在python中有个`heapq`可以直接实现堆.关于`heap`的详细用法可以看[这里][Link 2]  
我们把所有的数据都都放在堆中，然后直接返回最大的k个数据就可以了，时间复杂度是`Time complexity: O(M + klogM)`，总的时间复杂度为`O(N+M+klgM)`

#coding:utf-8
    #/bin/python
    
    import sys, os
    from collections import defaultdict
    import heapq
    
    def main():
        if len(sys.argv) != 2:
            print "Usage: python **.py topK"
            sys.exit(1)
        else:
            #print sys.argv
            k = int(sys.argv[1])
        res_dict = defaultdict(int)
        heap_res = []
        for line in sys.stdin:
            res_dict[line.strip()] += 1
        for 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   204
    10.197.92.207   202
    10.197.42.72    202
    10.197.195.77   201
    10.197.190.108  201
    10.197.49.128   200
    10.197.236.54   200
    10.197.223.59   200
    10.197.145.27   200
    10.197.43.98    199
    
    real    0m5.085s
    user    0m4.760s
    sys     0m0.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/python
    
    import sys, os
    from collections import defaultdict
    import heapq
    
    def 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()] += 1
        for 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   204
    10.197.92.207   202
    10.197.42.72    202
    10.197.195.77   201
    10.197.190.108  201
    10.197.49.128   200
    10.197.236.54   200
    10.197.223.59   200
    10.197.145.27   200
    10.197.43.98    199
    
    real    0m4.917s
    user    0m4.670s
    sys     0m0.220s

# 总结 #

如果我们处理大批量的数据时候，还是要学会优化代码，但是掌握`shell`的命令行使用方法，可以极大的提高我们的效率

# 参考链接 #

[十一、从头到尾解析Hash表算法][https_blog.csdn.net_v_JULY_v_article_details_6256463]  
[【原创】Python处理海量数据的实战研究][Python]  
[https://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/][https_www.geeksforgeeks.org_k-largestor-smallest-elements-in-an-array]

[https_blog.csdn.net_v_JULY_v_article_details_6256463]: https://blog.csdn.net/v_JULY_v/article/details/6256463
[Link 1]: http://www.benfrederickson.com/heap-visualization/
[Link 2]: https://docs.python.org/2/library/heapq.html
[Python]: https://blog.csdn.net/quicktest/article/details/7453189
[https_www.geeksforgeeks.org_k-largestor-smallest-elements-in-an-array]: https://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/