为什么比Python中的排序慢?

问题:

我发现max比Python 2和3中的sort函数慢。
Python 2

$ python -m timeit -s 'import random;a=range(10000);random.shuffle(a)' 'a.sort();a[-1]'
1000 loops, best of 3: 239 usec per loop
$ python -m timeit -s 'import random;a=range(10000);random.shuffle(a)' 'max(a)'        
1000 loops, best of 3: 342 usec per loop

Python 3

$ python3 -m timeit -s 'import random;a=list(range(10000));random.shuffle(a)' 'a.sort();a[-1]'
1000 loops, best of 3: 252 usec per loop
$ python3 -m timeit -s 'import random;a=list(range(10000));random.shuffle(a)' 'max(a)'
1000 loops, best of 3: 371 usec per loop

为什么is maxO(n))比sort功能(O(nlogn))慢?

回答:

在Python中使用timeit模块时,您必须非常小心。

python -m timeit -s 'import random;a=range(10000);random.shuffle(a)' 'a.sort();a[-1]'

这里初始化代码运行一次以产生随机数组a。然后代码的其余部分运行几次。第一次对数组进行排序,但是每隔一段时间,您都会在已排序的数组上调用排序方法。只有最快的时间才能返回,所以你实际上是在Python中排序已排序数组的时间。
Python的排序算法的一部分是检测数组何时已部分或完全排序。完全排序后,只需扫描一次即可检测数组,然后停止。
如果你试过:

python -m timeit -s 'import random;a=range(100000);random.shuffle(a)' 'sorted(a)[-1]'

那么排序会在每个时序循环中发生,您可以看到排序数组的时间确实比找到最大值要长得多。
 编辑: @ skyking的answer解释了我不明原因的部分:a.sort()知道它在列表中工作,所以可以直接访问元素。 max(a)可以任意任意迭代,因此必须使用泛型迭代。

 
 
Code问答: http://codewenda.com/topics/python/
Stackoverflow: Why is max slower than sort in Python?

*转载请注明本文链接以及stackoverflow的英文链接

发表评论

电子邮件地址不会被公开。 必填项已用*标注

61 + = 67