Python序列sort与bisect.insort及heapq.heappush哪种效率最高效,,import timei
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 本身的一些限制无法体现。
编橙之家文章,
相关内容
- Python有大数据处理性能优化好方法吗,python性能优化
- python requests发送post Page load erro问题,requestserro,post过去
- 想用powershell写命令完成启动软件和调用python脚本怎么做
- mac电脑不支持gbk,python post数据出现乱码怎么破?,gbkpy
- linux下想打包pyqt程序为可执行程序用什么工具?,lin
- python3 snmp都用什么扩展模块,python3snmp,最近用flask弄了
- Python执行mysql语句time时间不正确何解,pythonmysql,类库
- 求Python实现跨平台实现全局性一句话方法,python全局性
- Python引用传递是在什么场景下,python引用传递场景,我写
- 要删除str数据类型中的冒号,用re正则方式应该怎么写
评论关闭