为什么 max 比 sort 慢？
Why is max slower than sort?
我发现 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
为什么是max（O(n)）比sort函数（O(nlogn)）慢？
在Python中使用timeit模块时必须非常小心。
python -m timeit -s 'import random;a=range(10000);random.shuffle(a)' 'a.sort();a[-1]'
这里的初始化代码运行s一次产生一个随机数组a。然后剩下的代码就是运行几次。第一次对数组进行排序，但每隔一次你就在一个已经排序的数组上调用 sort 方法。仅返回最快的时间，因此您实际上是在计算 Python 对已排序的数组进行排序所需的时间。
Python 的部分排序算法用于检测数组何时已部分或完全排序。完全排序后，它只需扫描一次数组即可检测到这一点，然后停止。
如果您尝试过：
python -m timeit -s 'import random;a=range(100000);random.shuffle(a)' 'sorted(a)[-1]'
然后排序在每个时序循环中发生，你可以看到排序数组的时间确实比只找到最大值要长得多。
编辑： @skyking 的 解释了我未解释的部分：a.sort() 知道它正在处理列表，因此可以直接访问元素。 max(a) 适用于任意可迭代对象，因此必须使用通用迭代。
这可能是因为 l.sort 是 list 的成员，而 max 是通用函数。这意味着 l.sort 可以依赖 list 的内部表示，而 max 必须通过通用迭代器协议。
这使得 l.sort 的每个元素获取比 max 的每个元素获取更快。
我假设如果您改为使用 sorted(a)，您得到的结果会比 max(a) 慢。
首先，请注意 max() uses the iterator protocol, while list.sort() uses ad-hoc code。显然，使用迭代器是一项重要的开销，这就是为什么您观察到时间差异的原因。
但是，除此之外，您的测试并不公平。您不止一次在同一个列表中 运行宁 a.sort()。 algorithm used by 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日志n。它甚至并不意味着它需要比 O(n) 算法慢，但那是另一回事了。重要的是要理解，在某些有利的情况下，O(n log n) 算法可能 运行 在 O(n) 次或更少.
我发现 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
为什么是max（O(n)）比sort函数（O(nlogn)）慢？
在Python中使用timeit模块时必须非常小心。
python -m timeit -s 'import random;a=range(10000);random.shuffle(a)' 'a.sort();a[-1]'
这里的初始化代码运行s一次产生一个随机数组a。然后剩下的代码就是运行几次。第一次对数组进行排序，但每隔一次你就在一个已经排序的数组上调用 sort 方法。仅返回最快的时间，因此您实际上是在计算 Python 对已排序的数组进行排序所需的时间。
Python 的部分排序算法用于检测数组何时已部分或完全排序。完全排序后，它只需扫描一次数组即可检测到这一点，然后停止。
如果您尝试过：
python -m timeit -s 'import random;a=range(100000);random.shuffle(a)' 'sorted(a)[-1]'
然后排序在每个时序循环中发生，你可以看到排序数组的时间确实比只找到最大值要长得多。
编辑： @skyking 的 a.sort() 知道它正在处理列表，因此可以直接访问元素。 max(a) 适用于任意可迭代对象，因此必须使用通用迭代。
这可能是因为 l.sort 是 list 的成员，而 max 是通用函数。这意味着 l.sort 可以依赖 list 的内部表示，而 max 必须通过通用迭代器协议。
这使得 l.sort 的每个元素获取比 max 的每个元素获取更快。
我假设如果您改为使用 sorted(a)，您得到的结果会比 max(a) 慢。
首先，请注意 max() uses the iterator protocol, while list.sort() uses ad-hoc code。显然，使用迭代器是一项重要的开销，这就是为什么您观察到时间差异的原因。
但是，除此之外，您的测试并不公平。您不止一次在同一个列表中 运行宁 a.sort()。 algorithm used by 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日志n。它甚至并不意味着它需要比 O(n) 算法慢，但那是另一回事了。重要的是要理解，在某些有利的情况下，O(n log n) 算法可能 运行 在 O(n) 次或更少.