为什么max比排序慢？

Question

我发现 max 比 Python 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

蟒蛇 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

为什么＜code＞max＜/code＞（＜code＞O（n）＜/code>）比＜code＞sort＜/code＞函数（＜code＜O（nlogn）＜/code＞）慢？

Answer 1

这可能是因为l.sort是list的成员，而max是泛型函数。这意味着l.sort可以依赖list的内部表示，而max必须通过泛型迭代器协议。

这使得 l.sort 的每个元素提取都比 max 的每个元素获取更快。

我假设如果你改用sorted（a），你会得到比max（a）慢的结果。

Answer 2

首先，请注意max（）使用迭代器协议，而list.sort（）使用即席代码。显然，使用迭代器是一个重要的开销，这就是您观察时间差异的原因。

但是，除此之外，您的测试是不公平的。您多次在同一列表上运行 a.sort（）。Python 使用的算法专门设计为对已经（部分）排序的数据快速处理。您的测试表明该算法正在很好地完成其工作。

这些是公平的测试：

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

在这里，我每次都创建一个列表的副本。正如你所看到的，结果的数量级是不同的：如我们所预期的，微秒与毫秒。

记住:big-Oh指定了一个上限！Python的排序算法的下限是ω(n)。成为O(n log n)并不自动意味着每次运行花费的时间与n log n成比例。它甚至不意味着它需要比O(n)算法慢，但那是另一个故事。重要的是要理解，在一些有利的情况下，O(n log n)算法可以在O(n)时间或更短时间内运行。

Answer 3

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

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

这里，初始化代码运行一次，以产生随机数组< code>a。然后剩余的代码运行几次。第一次它对数组进行排序，但是每隔一次你在一个已经排序的数组上调用sort方法。只返回最快的时间，所以您实际上是在计时Python对一个已经排序的数组进行排序需要多长时间。

Python排序算法的一部分是检测数组何时已经部分或完全排序。当完全排序后，它只需扫描一次数组来检测这一点，然后停止。

如果您尝试：

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

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

编辑：@skyking的回答解释了我未解释的部分：a.sort（） 知道它正在处理列表，因此可以直接访问元素。max（a） 适用于任何任意可迭代对象，因此必须使用泛型迭代。