为什么 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() returns 一个 新的、复制和排序的列表 而不是就地排序：

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

为什么 python 需要更长的时间来排序列表的副本？

why does python takes longer time to sort a copy of list?

python

performance

sorting

timeit