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

标签: python 大数据 topk | 发表时间:2014-11-22 02:17 | 作者:u010180339
出处:http://blog.csdn.net

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 原文链接
阅读:36 评论:0 查看评论

相关 [python 大数据 topk] 推荐:

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

- - CSDN博客推荐文章
TopK问题,即寻找最大的K个数,这个问题非常常见,比如从1千万搜索记录中找出最热门的10个关键词.. 先排序,然后截取前k个数.. 时间复杂度:O(n*logn)+O(k)=O(n*logn). 维护容量为k的最小堆.根据最小堆性质,堆顶一定是最小的,如果小于堆顶,则直接pass,如果大于堆顶,则替换掉堆顶,并heapify整理堆,其中heapify的时间复杂度是logk..

Java最小堆解决TopK问题

- - ITeye博客
其实我们与大数据并不遥远,比如要从海量数据中按大小或频率挑出top k,假定机器是多核的内存有限的,我们采用多线程分块处理数据,最后合并处理. 那么,处理每一块数据的top k(i)可以采用哪些算法呢. TopK问题是指从大量数据(源数据)中获取最大(或最小)的K个数据. TopK问题是个很常见的问题:例如学校要从全校学生中找到成绩最高的500名学生,再例如某搜索引擎要统计每天的100条搜索次数最多的关键词.

dropbox讲python

- chuang - Initiative
dropbox定制优化CPython虚拟机,自己搞了个malloc调度算法. 那个 !!!111cos(0). 期待这次PyCon China 2011.

Python调试

- - 企业架构 - ITeye博客
原文地址: http://blog.csdn.net/xuyuefei1988/article/details/19399137. 1、下面网上收罗的资料初学者应该够用了,但对比IBM的Python 代码调试技巧:. IBM:包括 pdb 模块、利用 PyDev 和 Eclipse 集成进行调试、PyCharm 以及 Debug 日志进行调试:.

Python WSGI 初探

- - 坚实的幻想
在构建 Web 应用时,通常会有 Web Server 和 Application Server 两种角色. 其中 Web Server 主要负责接受来自用户的请求,解析 HTTP 协议,并将请求转发给 Application Server,Application Server 主要负责处理用户的请求,并将处理的结果返回给 Web Server,最终 Web Server 将结果返回给用户.

Python实现逻辑回归(Logistic Regression in Python)

- - 神刀安全网
Logistic Regression in Python ,作了中文翻译,并相应补充了一些内容. 本文并不研究逻辑回归具体算法实现,而是使用了一些算法库,旨在帮助需要用Python来做逻辑回归的训练和预测的读者快速上手. 逻辑回归是一项可用于预测二分类结果(binary outcome)的统计技术,广泛应用于金融、医学、犯罪学和其他社会科学中.

python 下载文件

- Eric - python相关的python 教程和python 下载你可以在老王python里寻觅
之前给大家分享的python 多线程抓取网页,我觉的大家看了以后,应该会对python 抓取网页有个很好的认识,不过这个只能用python 来抓取到网页的源代码,如果你想用做python 下载文件的话,上面的可能就不适合你了,最近我在用python 做文件下载的时候就遇到这个问题了,不过最终得以解决,为了让大家以后碰过这个问题有更好的解决办法,我把代码发出来:.

python代码调试

- - 阿里古古
【转自: http://blog.csdn.net/luckeryin/article/details/4477233】. 本文讨论在没有方便的IDE工具可用的情况下,使用pdb调试python程序. 例如,有模拟税收计算的程序:. debug_demo函数计算4500的入账所需的税收. 在需要插入断点的地方,加入红色部分代码:如果_DEBUG值为True,则在该处开始调试(加入_DEBUG的原因是为了方便打开/关闭调试).

python编程规范

- - 互联网 - ITeye博客
@FileName: @Author:xx@ic.net.cn @Create date: @description:用一行文字概述模块或脚本,用句号结尾. 不影响编码的效率,不与大众习惯冲突.. 使代码的逻辑更清晰,更易于理解..   *所有的 Python 脚本文件都应在文件头标上如下标识或其兼容格式的标识.

《Dive into Python 3》中文版

- hama - Wow! Ubuntu
Dive Into Python 是一份很知名的 Python 入门教程,由 Mark Pilgrim 编写,用户可以免费获取电子版本,而中文版则由啄木鸟社区翻译发布 [ 英文版 / 中文版 ]. 前阵子,Mark Pilgrim 又发布了 《Dive into Python 3》,此版本的内容涵盖了 Python 3 及其与 Python 2 的区别.