![]() | 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 ![]() @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-2-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' |
![]() | 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)呐。。 |