为什么 max 比 sort 慢？

我发现max比sortPython 2 和 3 中的函数。

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

Why is max (O(n)）慢于sort功能 （O(nlogn))?

使用时必须非常小心timeitPython 中的模块。

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]'

然后排序发生在每个定时循环上，您可以看到对数组进行排序的时间确实比仅找到最大值要长得多。

Edit:@skyking的answer https://stackoverflow.com/a/35015156/641833解释了我未解释的部分：a.sort()知道它正在处理列表，因此可以直接访问元素。max(a)适用于任何任意迭代，因此必须使用通用迭代。