你好,游客 登录
背景:
阅读新闻

飘逸的python-大数据TopK问题的quick select解法

[日期:2014-11-24] 来源:IT 社区  作者:u010180339 [字体: ]

    TopK问题,即寻找最大的K个数,这个问题非常常见,比如从1千万搜索记录中找出最热门的10个关键词.

方法一:

    先排序,然后截取前k个数.

    时间复杂度:O(n*logn)+O(k)=O(n*logn)。

方法二:

    最小堆.

    维护容量为k的最小堆.根据最小堆性质,堆顶一定是最小的,如果小于堆顶,则直接pass,如果大于堆顶,则替换掉堆顶,并heapify整理堆,其中heapify的时间复杂度是logk.

    时间复杂度:O(k+(n-k)*logk)=O(n*logk)

方法三:

    本文的主角.quick select算法.其实就类似于快排.不同地方在于quick select每趟只需要往一个方向走.

    时间复杂度:O(n).

def qselect(A,k):
    if len(A)<k:return A
    pivot = A[-1]
    right = [pivot] + [x for x in A[:-1] if x>=pivot]
    rlen = len(right)
    if rlen==k:
        return right
    if rlen>k:
        return qselect(right, k)
    else:
        left = [x for x in A[:-1] if x<pivot]
        return qselect(left, k-rlen) + right

for i in range(1, 10):
    print qselect([11,8,4,1,5,2,7,9], i)

作者:u010180339 发表于2014-11-21 18:17:08 原文链接




收藏 推荐 打印 | 录入: | 阅读:
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数
点评:
       
评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款