import time import bisect,heapq,random def sort1(n): "sort1 : bisect" lst = [] for i in xrange(n): bisect.insort_left(lst,random.randint(1,10000)) return lst def sort2(n): "sort2 :lst.sort" lst = [] for i in xrange(n): lst.append(random.randint(1,10000)) lst.sort() return lst def sort3(n): "sort3 : heapq" lst = [] for i in xrange(n): heapq.heappush(lst,random.randint(1,10000)) return lst for 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.49 sort2 :lst.sort 0.36 sort3 : heapq 0.42
为什么bisect, heapq
反而比内置方法 sort 还要慢?
1.
bisect
根据
insort_left
的文档:也就是说,单次
insort_left
的时间复杂度是O(n)
,自然sort1
的复杂度就变成了O(n^2)
,它最慢是应当的。2.
sort
文档说是
O(n log n)
的复杂度。从 listsort 详细文档来看,开发人员着实没少下了工夫。3.
heappush
根据维基百科,插入操作的时间复杂度是
O(log n)
,所以总的时间复杂度仍然是O(n log n)
。不过有一点值得注意,插入操作的平均时间是O(1)
,所以有可能会稍微快一点。Python vs. PyPy
CPython 2.7
PyPy 2.4
注,我把你的调用部分复制了一遍,执行了两次,结果为第二次的输出。
可以看得出,
O(n log n)
算法的耗时是在同一个数量级上的,但 CPython 中sort
胜出,PyPy 中heapq
胜出。cProfile
用
cProfile
来测试,先看一下 CPython 的结果:CPython
lst.sort
:CPython
heapq
:可以看出,相同操作消耗的时间差不太多,不同的地方在于
sort
用了62ms
、append
用了71ms
,总共是133ms
;而相比之下,heappush
用了210ms
。再根据之前 PyPy 的迹象,这里怀疑 CPython 和heapq
的 C 实现在多次互相调用中有一些解释器相关的“额外”代码。最后再看一下 PyPy 的情况。
PyPy
lst.sort
:PyPy
heapq
:情况发生了变化!PyPy 的
heapq
实现是纯 Python 的,依托 PyPy 的性能来达到飞一般的效果。不过,在增加了cProfile
的钩子之后,大量的函数调用计数变成了瓶颈,增加了heapq
算法的时间消耗。总结
n^2
的算法毋庸置疑最慢,但同样是n log n
,依次插入方式的堆排序可能会比内置的sort
函数稍快一些,但因为 CPython 本身的一些限制无法体现。