なぜ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のソートアルゴリズム）から

：

アルゴリズムがすでに順序付けられているデータのサブシーケンスを見つけ、そしてより効率的に残りをソートするためにその知識を使用します。言い換えれば

それはきれいで、ソートされていないリストを毎回与えられているので、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