1
ThunderEX 2013-02-26 13:45:13 +08:00
不是有max()嘛
|
2
phuslu 2013-02-26 14:24:07 +08:00
直接用 collections.Counter 不行吗?
|
4
paramiao OP @phuslu 主要是元数据结构比较复杂,不是单纯的list or dict,是比较复杂的json数据,所以需要自己去count然后sort,如果转的话也行但是会造成内存空间占用比较大,因为冗余字段会变多
|
5
keakon 2013-02-26 15:09:16 +08:00
@paramiao heapq.nlargest()
你最好 cProfile 一下看看瓶颈在哪。有次我把 nlargest() 和 sorted() 来比较,发现用的时间基本没差别。最后看了下排序的时间分别为 0.001 和 0.003 秒,而 IO 和其他计算时间是超过 1 秒的,当然看不出差距… |
6
paramiao OP @keakon 我和你说的情况一样,不过我统计的没有包括IO和其他计算,所以我总觉得是heapq的实现问题,heapq是不是本身就是通过python实现的,没有原生C写的排序性能好呢?
|
7
phuslu 2013-02-26 15:42:28 +08:00 2
@paramiao heapq.nlargest 不要传 key 参数. 传了话就是用 pure python 代码来排序。
你可以实现 __cmp__, 然后调用试下 :D |
8
brucexin 2013-02-26 16:59:55 +08:00
不能从原数据构造出索引吗?
|
9
paramiao OP @brucexin 可以啊,一般排序通过key都可以使用,但是问题是构造索引时,其他的属性或字段不能扔掉,因为数据比较大,这样占用内存会很大
|
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。 我这边测试,会快很多。 |
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' |
12
Parallel 2013-03-08 18:20:35 +08:00
python的堆排肯定不如C或C++的快啊。。
自己敲一个堆排试试。。 |
13
Parallel 2013-03-08 18:23:25 +08:00
另外堆排的最坏时间复杂度是nlog(n)呐。。
|