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

为什么排序x和y时有太大的区别，y只是x的副本？ python不是马上复制列表吗？为什么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

来源

2016-09-19 mohit

@MartijnPieters他在第一个上做了一个副本。 – Bharel

@ njzk2：不，相反。它应该是测试的一部分，这就是整个观点。 –

你的第一个和最后的例子有对列表进行排序只有一次。之后，Python使用的排序算法有一个简单的时间，因为它被优化以利用已排序的序列。

从Wikipedia article on 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

来源

2016-09-19 20:35:08

有兴趣的读者可以另外加一个：对于时间比较，应该使用'sorted'（它不会在原地排序），或者将随机列表的创建放入测试中（但这有时会破坏定时）。 – MSeifert

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

回答

相关问题