Python序列sort与bisect.insort及heapq.heappush哪种效率最高效,,import timei


import timeimport bisect,heapq,randomdef sort1(n):    "sort1 : bisect"    lst = []    for i in xrange(n):        bisect.insort_left(lst,random.randint(1,10000))    return lstdef sort2(n):    "sort2 :lst.sort"    lst = []    for i in xrange(n):        lst.append(random.randint(1,10000))    lst.sort()    return lstdef sort3(n):    "sort3 : heapq"    lst = []    for i in xrange(n):        heapq.heappush(lst,random.randint(1,10000))    return lstfor i in [sort1,sort2,sort3]:    time1 = time.clock()    i(100000)    time2 = time.clock()    time_all = time2-time1    print i.__doc__,time_all

输出结果:

sort1 : bisect 2.49sort2 :lst.sort 0.36sort3 : heapq 0.42

为什么 bisect, heapq 反而比内置方法 sort 还要慢?

根据insort_left 的文档:

也就是说,单次 insort_left 的时间复杂度是 O(n),自然 sort1 的复杂度就变成了 O(n^2),它最慢是应当的。

文档说是 O(n log n) 的复杂度。从 listsort 详细文档来看,开发人员着实没少下了工夫。

根据维基百科,插入操作的时间复杂度是 O(log n),所以总的时间复杂度仍然是 O(n log n)。不过有一点值得注意,插入操作的平均时间是 O(1),所以有可能会稍微快一点。

Python vs. PyPy

CPython 2.7

sort1 : bisect 2.617674sort2 :lst.sort 0.295187sort3 : heapq 0.39279

PyPy 2.4

sort1 : bisect 1.31sort2 :lst.sort 0.043sort3 : heapq 0.029

注,我把你的调用部分复制了一遍,执行了两次,结果为第二次的输出。

可以看得出,O(n log n) 算法的耗时是在同一个数量级上的,但 CPython 中 sort 胜出,PyPy 中 heapq 胜出。

cProfile

用 cProfile 来测试,先看一下 CPython 的结果:

CPython lst.sort:

         400007 function calls in 0.935 seconds   Ordered by: internal time   ncalls  tottime  percall  cumtime  percall filename:lineno(function)   100000    0.325    0.000    0.386    0.000 random.py:175(randrange)        1    0.211    0.211    0.933    0.933 t.py:11(sort2)   100000    0.203    0.000    0.590    0.000 random.py:238(randint)   100000    0.071    0.000    0.071    0.000 {method 'append' of 'list' objects}        1    0.062    0.062    0.062    0.062 {method 'sort' of 'list' objects}   100000    0.061    0.000    0.061    0.000 {method 'random' of '_random.Random' objects}

CPython heapq:

         400006 function calls in 1.091 seconds   Ordered by: internal time   ncalls  tottime  percall  cumtime  percall filename:lineno(function)   100000    0.348    0.000    0.439    0.000 random.py:175(randrange)        1    0.228    0.228    1.089    1.089 t.py:19(sort3)   100000    0.212    0.000    0.651    0.000 random.py:238(randint)   100000    0.210    0.000    0.210    0.000 {_heapq.heappush}   100000    0.091    0.000    0.091    0.000 {method 'random' of '_random.Random' objects}

可以看出,相同操作消耗的时间差不太多,不同的地方在于 sort 用了 62ms、append 用了 71ms,总共是 133ms;而相比之下,heappush 用了 210ms。再根据之前 PyPy 的迹象,这里怀疑 CPython 和 heapq 的 C 实现在多次互相调用中有一些解释器相关的“额外”代码。

最后再看一下 PyPy 的情况。

PyPy lst.sort:

         400007 function calls in 0.071 seconds   Ordered by: internal time   ncalls  tottime  percall  cumtime  percall filename:lineno(function)        1    0.025    0.025    0.071    0.071 t.py:11(sort2)        1    0.018    0.018    0.018    0.018 {method 'sort' of 'list' objects}   100000    0.011    0.000    0.019    0.000 random.py:172(randrange)   100000    0.008    0.000    0.008    0.000 {method 'random' of 'Random' objects}   100000    0.006    0.000    0.006    0.000 {method 'append' of 'list' objects}   100000    0.005    0.000    0.023    0.000 random.py:235(randint)

PyPy heapq:

         1156196 function calls in 0.171 seconds   Ordered by: internal time   ncalls  tottime  percall  cumtime  percall filename:lineno(function)        1    0.047    0.047    0.171    0.171 t.py:19(sort3)   100000    0.034    0.000    0.070    0.000 heapq.py:242(_siftdown)   228095    0.031    0.000    0.036    0.000 heapq.py:135(cmp_lt)   100000    0.013    0.000    0.013    0.000 {method 'append' of 'list' objects}   100000    0.012    0.000    0.098    0.000 heapq.py:140(heappush)   100000    0.011    0.000    0.017    0.000 random.py:172(randrange)   100000    0.009    0.000    0.026    0.000 random.py:235(randint)   100000    0.006    0.000    0.006    0.000 {method 'random' of 'Random' objects}   228095    0.005    0.000    0.005    0.000 {hasattr}   100000    0.002    0.000    0.002    0.000 {len}

情况发生了变化!PyPy 的 heapq 实现是纯 Python 的,依托 PyPy 的性能来达到飞一般的效果。不过,在增加了 cProfile 的钩子之后,大量的函数调用计数变成了瓶颈,增加了 heapq 算法的时间消耗。

总结

n^2 的算法毋庸置疑最慢,但同样是 n log n,依次插入方式的堆排序可能会比内置的 sort 函数稍快一些,但因为 CPython 本身的一些限制无法体现。

编橙之家文章,

评论关闭