python - 为什么Python需要更长的时间来对列表的副本进行排序？

Question

为什么对 x 和 y 进行排序时会有如此大的差异，而 y 只是 x 的副本？ python 不会立即复制列表吗？

python -mtimeit -s'import random; x=range(1000); random.shuffle(x)' 'y=list(x); x.sort()'
100000 loops, best of 3: 19.5 usec per loop
python -mtimeit -s'import random; x=range(1000); random.shuffle(x)' 'y=list(x); y.sort()'
1000 loops, best of 3: 211 usec per loop
python -mtimeit -s'import random; x=range(1000); random.shuffle(x)' 'x.sort()'
100000 loops, best of 3: 15.9 usec per loop

Answer 1

您的第一个和最后一个示例必须对列表仅排序一次。之后，Python 使用的排序算法就很简单了，因为它经过优化可以利用已经排序的序列。

来自Wikipedia article on TimSort (Python排序算法):

The algorithm finds subsequences of the data that are already ordered, and uses that knowledge to sort the remainder more efficiently.

换句话说，list(y); y.sort() 情况是不利的，因为它每次都会得到一个干净的、未排序的列表。 x.sort() 情况给出一个完全排序的列表(在第一次迭代之后)。毕竟，list.sort() 会就地进行排序，从而改变列表。 timeit 测试不会为每个测试创建副本，因此后续测试会重复使用相同的列表。

如果您改用 sorted() 函数，您将不再看到时间优势，因为 sorted() 返回一个新的、复制的和排序列表而不是就地排序:

python -mtimeit -s'import random; x=range(1000); random.shuffle(x)' 'y=list(x); sorted(x)'
10000 loops, best of 3: 151 usec per loop
python -mtimeit -s'import random; x=range(1000); random.shuffle(x)' 'y=list(x); sorted(y)'
10000 loops, best of 3: 155 usec per loop
python -mtimeit -s'import random; x=range(1000); random.shuffle(x)' 'sorted(x)'
10000 loops, best of 3: 152 usec per loop