为什么python需要更长的时间来排序list的副本?

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使用的排序算法就很容易了，因为它已经优化了已经排序的序列。

摘自维基百科关于TimSort (Python排序算法)的文章:

该算法查找已经排序的数据的子序列，并使用该知识对剩余的数据进行更有效的排序。

换句话说，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