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

一些数据需要先进行循环统计某些字段重复项，大概需要5次排序，找出5个字段重复项较多的数据，开始时我用的是python的sorted函数，后来发现当数据到百万级别时，单机计算需要以小时为单位了，然后优化时考虑到只取排序后较大数据，就改用最大堆排序，python的heapq模块，结果发现并没优化太多，求解？

排序

Python

sorted

13 条回复 • 1970-01-01 08:00:00 +08:00

ThunderEX

2013-02-26 13:45:13 +08:00

不是有max()嘛

phuslu

2013-02-26 14:24:07 +08:00

直接用 collections.Counter 不行吗？

paramiao

2013-02-26 14:43:39 +08:00

@ThunderEX max不是最大的一个数据吗？我需要的是100万中最大的50个

paramiao

2013-02-26 15:01:55 +08:00

@phuslu 主要是元数据结构比较复杂，不是单纯的list or dict，是比较复杂的json数据，所以需要自己去count然后sort，如果转的话也行但是会造成内存空间占用比较大，因为冗余字段会变多

keakon

2013-02-26 15:09:16 +08:00

@paramiao heapq.nlargest()

你最好 cProfile 一下看看瓶颈在哪。有次我把 nlargest() 和 sorted() 来比较，发现用的时间基本没差别。最后看了下排序的时间分别为 0.001 和 0.003 秒，而 IO 和其他计算时间是超过 1 秒的，当然看不出差距…

paramiao

2013-02-26 15:35:28 +08:00

@keakon 我和你说的情况一样，不过我统计的没有包括IO和其他计算，所以我总觉得是heapq的实现问题，heapq是不是本身就是通过python实现的，没有原生C写的排序性能好呢？

phuslu

2013-02-26 15:42:28 +08:00

@paramiao heapq.nlargest 不要传 key 参数. 传了话就是用 pure python 代码来排序。
你可以实现 __cmp__，然后调用试下：D

brucexin

2013-02-26 16:59:55 +08:00

不能从原数据构造出索引吗？

paramiao

2013-02-26 17:09:36 +08:00

@brucexin 可以啊，一般排序通过key都可以使用，但是问题是构造索引时，其他的属性或字段不能扔掉，因为数据比较大，这样占用内存会很大

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

2013-02-26 21:36:36 +08:00

@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

2013-03-08 18:20:35 +08:00

python的堆排肯定不如C或C++的快啊。。
自己敲一个堆排试试。。

Parallel

2013-03-08 18:23:25 +08:00

另外堆排的最坏时间复杂度是nlog(n)呐。。