V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
paramiao
V2EX  ›  Python

python的sorted排序和heapq排序,在排序找出最大项时,有关性能的问题。

  •  
  •   paramiao · 2013-02-26 13:42:26 +08:00 · 6059 次点击
    这是一个创建于 4270 天前的主题,其中的信息可能已经有所发展或是发生改变。
    一些数据需要先进行循环统计某些字段重复项,大概需要5次排序,找出5个字段重复项较多的数据,开始时我用的是python的sorted函数,后来发现当数据到百万级别时,单机计算需要以小时为单位了,然后优化时考虑到只取排序后较大数据,就改用最大堆排序,python的heapq模块,结果发现并没优化太多,求解?
    13 条回复    1970-01-01 08:00:00 +08:00
    ThunderEX
        1
    ThunderEX  
       2013-02-26 13:45:13 +08:00
    不是有max()嘛
    phuslu
        2
    phuslu  
       2013-02-26 14:24:07 +08:00
    直接用 collections.Counter 不行吗?
    paramiao
        3
    paramiao  
    OP
       2013-02-26 14:43:39 +08:00
    @ThunderEX max不是最大的一个数据吗?我需要的是100万中最大的50个
    paramiao
        4
    paramiao  
    OP
       2013-02-26 15:01:55 +08:00
    @phuslu 主要是元数据结构比较复杂,不是单纯的list or dict,是比较复杂的json数据,所以需要自己去count然后sort,如果转的话也行但是会造成内存空间占用比较大,因为冗余字段会变多
    keakon
        5
    keakon  
       2013-02-26 15:09:16 +08:00
    @paramiao heapq.nlargest()

    你最好 cProfile 一下看看瓶颈在哪。有次我把 nlargest() 和 sorted() 来比较,发现用的时间基本没差别。最后看了下排序的时间分别为 0.001 和 0.003 秒,而 IO 和其他计算时间是超过 1 秒的,当然看不出差距…
    paramiao
        6
    paramiao  
    OP
       2013-02-26 15:35:28 +08:00
    @keakon 我和你说的情况一样,不过我统计的没有包括IO和其他计算,所以我总觉得是heapq的实现问题,heapq是不是本身就是通过python实现的,没有原生C写的排序性能好呢?
    phuslu
        7
    phuslu  
       2013-02-26 15:42:28 +08:00   ❤️ 2
    @paramiao heapq.nlargest 不要传 key 参数. 传了话就是用 pure python 代码来排序。
    你可以实现 __cmp__, 然后调用试下 :D
    brucexin
        8
    brucexin  
       2013-02-26 16:59:55 +08:00
    不能从原数据构造出索引吗?
    paramiao
        9
    paramiao  
    OP
       2013-02-26 17:09:36 +08:00
    @brucexin 可以啊,一般排序通过key都可以使用,但是问题是构造索引时,其他的属性或字段不能扔掉,因为数据比较大,这样占用内存会很大
    jk2r
        10
    jk2r  
       2013-02-26 19:01:50 +08:00
    首先,heapq确实是用python写的。如果5个字段都分别存入,这个消耗确实很大(冗余)。
    建议先time python *.py调试一下代码,看看主要耗时在哪。
    索引可以这样做:原文一个key-value,5个字段分别存5个key(hash字段)-list(count,原文key数组)。这样可以保证,500万的数据只有一次线性扫描,扫描过程中,解json串存k-list。
    我这边测试,会快很多。
    keakon
        11
    keakon  
       2013-02-26 21:36:36 +08:00   ❤️ 1
    @jk2r 是有C版本的哦
    >>> import _heapq
    >>> dir(_heapq)
    ['__about__', '__doc__', '__file__', '__name__', '__package__', 'heapify', 'heappop', 'heappush', 'heappushpop', 'heapreplace', 'nlargest', 'nsmallest']
    >>> _heapq.__file__
    '/System/Library/Frameworks/Python.framework/Versions/2.7/lib/python2.7/lib-dynload/_heapq.so'
    Parallel
        12
    Parallel  
       2013-03-08 18:20:35 +08:00
    python的堆排肯定不如C或C++的快啊。。
    自己敲一个堆排试试。。
    Parallel
        13
    Parallel  
       2013-03-08 18:23:25 +08:00
    另外堆排的最坏时间复杂度是nlog(n)呐。。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5772 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 02:53 · PVG 10:53 · LAX 18:53 · JFK 21:53
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.