在Python中排序列表时传递reverse=True会影响效率吗？

Question

在Python中，当你对一个列表使用sort()方法时，如果你传入cmp=f，会让排序变得更慢。那么，传入reverse=True会对排序的效率有影响吗？还是说它和不反转排序的情况是一样的呢？

Answer 1

sort() 方法是原生的，也就是说它是在主语言中实现的，而不是用 Python 写的。如果你在 cmp 参数中传入一个函数，那么这个原生的实现就会在每次排序时调用这个函数，并执行 Python 代码。这就是为什么性能会下降的原因。

另一方面，如果你在 reverse 参数中传入 True，那么它只是告诉原生算法要反向排序。如果没有设置 cmp，那么就只会用原生代码进行排序，所以性能应该和普通的 sort() 差不多。

当然，做一些基准测试可以更准确地判断。

Answer 2

根据我的测试，似乎有一点小差别：

import timeit

setup = """
import random
random.seed(1)
l = range(10000)
random.shuffle(l)
"""

run1 = """
sorted(l)
"""

run2 = """
sorted(l, reverse=True)
"""

n1 = timeit.timeit(run1, setup, number=10000)
n2 = timeit.timeit(run2, setup, number=10000)

print n1, n2
print (n2/n1 - 1)*100,"%"

在我的电脑上得到的结果：

38.8531708717 41.2889549732
6.26920286513 %

同样的测试，不过是对一个包含1000个元素的列表：

2.80148005486 2.74061703682
-2.17253083528 %

# ...another round...
2.90553498268 2.86594104767
-1.36270722083 %

Answer 3

我猜使用 reverse=True 并不会导致速度变慢，因为结果可以在过程中通过反向的决策来构建。经过正确的基准测试（感谢Duncan），这个猜测得到了验证：

In [18]: import random

In [57]: x = range(1000)

In [58]: random.shuffle(x)

In [59]: %timeit sorted(x)
1000 loops, best of 3: 341 us per loop

In [54]: x = range(1000)

In [55]: random.shuffle(x)

In [56]: %timeit sorted(x, reverse = True)
1000 loops, best of 3: 344 us per loop

我已经多次重复这个测试，并且使用了不同大小的列表（N = 10**3, 10**4, 10**5），结果都很一致。