在Python中对列表进行排序时使用reverse=True会影响效率吗？

Question

在Python中对列表调用sort()函数时，传递cmp=f会减慢排序速度。如果传递reverse=True，是否会以任何方式影响排序的效率（或者与不反转排序相同）？

- jrdioko

---

对于一个有趣且有用的问题，将会额外加上0.75分；如果正确使用了单词“affect”，则将会额外加上0.25分。 - Justin ᚅᚔᚈᚄᚒᚔ

Answer 1

我猜测由于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），并得到了一致的结果。

- unutbu

---

我认为你的基准测试有问题。你应该尝试计时sorted(x)，否则它只会对已排序的列表进行一次排序，然后计算排序或反向排序所需的时间。当我使用sorted(x)进行基准测试时，每个循环需要4.41毫秒，而反向排序与排序没有区别，而x.sort()则需要249微秒/262微秒。 - Duncan

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 %

- GaretJax

---

每次对相同的列表进行排序并不能证明任何差异，因为排序时间会取决于数据分布。 - Mark Ransom

Answer 3

sort() 方法是本地方法，即它是在主机语言中实现而不是在 Python 中实现的。在 cmp 参数中传递一个函数会强制使用本地实现调用该函数并在每次迭代时执行 Python 代码。这就是性能损失的来源。

另一方面，在 reverse 参数中传递 True 只会指示本地算法以相反顺序对项目进行排序。如果未设置 cmp 参数，则仅涉及本地代码，因此性能应与普通的 sort() 相当。

当然，基准测试才能确定结果。

- Frédéric Hamidi

Answer 4

令人惊讶的是，对列表进行反向排序需要更长的时间。其他回答已经用不错的基准测试说明了这一点。我查看了源代码，并在 listobject.c 的解释 中找到了原因：

/* Reverse sort stability achieved by initially reversing the list,
applying a stable forward sort, then reversing the final result. */
if (reverse) {
    if (keys != NULL)
        reverse_slice(&keys[0], &keys[saved_ob_size]);
    reverse_slice(&saved_ob_item[0], &saved_ob_item[saved_ob_size]);
}

因此，要得到排序后的输出，需要在排序之前反转列表，然后再次排序，最后再次反转。反转列表是一个O(n)操作，因此，列表越长，您需要付出的代价就越多。

这表明，如果您已经在构建自定义键函数，那么可以通过直接取反来节省大型列表的时间：

very_long_list.sort(key=lambda x, y: -cmp(x, y))

不要使用reversed=True，而应该：

very_long_list.sort(key=lambda x, y: cmp(x, y), reverse=True)

在这种情况下，你当然可以直接在第二个案例中传递key=cmp，从而节省通过lambda函数的额外调用。但如果你有一个更大的表达式，那么这可能会更有价值。

- Martin Geisler

---

请注意，如果您只是否定比较函数，反向排序将不再稳定。这就是为什么Python执行反向/排序/反向洗牌以保持稳定性的原因。 - Duncan

+1 感谢您进行代码探索。我还在下载压缩包中...;-) - GaretJax

@Duncan：你确定吗？我认为这不是真的：根据定义，sort(key=f)对于任何f都是稳定的，包括当f是一个否定比较函数的情况。看起来cpython代码执行双重反转，这样它就不必因为性能原因而否定比较函数的结果，但它可以这样做并且是正确的。不正确的是通过普通键进行稳定排序，然后翻转（在排序之前不翻转）。 - sdcvvc

@sdcvvc 不，我不确定。 - Duncan

Answer 5

请注意，在Python 2.x中，list.sort和内置函数sorted的cmp参数已被弃用，并且在Python 3.x中不再允许使用，因为它们会导致性能下降，正如您所注意到的那样。相反，您应该使用key参数来定义自定义排序顺序。

- Lawrence D'Oliveiro

---

真的吗，在所有2.x版本中都被弃用了吗？我有一本来自2.3和2.4时代的书，它解释并鼓励使用。 - jrdioko