Pythonでリストをソートすると効率に影響を与える場合、reverse = Trueを渡しますか？

Question

Pythonのリストでsort()を呼び出すと、cmp=fを渡すと並べ替えが遅くなります。 reverse=Trueを渡すことは、ソートの効率に何らかの影響を及ぼします（または、ソートしないでソートすることと同じです）？

Answer 1

sort()メソッドはネイティブです。つまり、Pythonではなくホスト言語で実装されています。 cmp引数に関数を渡すと、ネイティブ実装はその関数を呼び出して各繰り返しでPythonコードを実行します。それはパフォーマンスのヒットから来ています。

一方、引数にTrueを渡しても、ネイティブアルゴリズムは逆にアイテムをソートするよう指示します。 cmpが設定されていない場合は、ネイティブコードのみが含まれるため、パフォーマンスは平文sort()に匹敵するはずです。

もちろん、ベンチマークによって確実にわかります。

Answer 2

reverse=Trueのためにスローダウンが発生していないと推測します。その結果は、途中で逆の決定で単純に構築できるためです。 （おかげでダンカンに）正確にベンチマークすると、この推測が裏付けされています。私はこのテストを数回繰り返し、異なるサイズのリスト（N = 10**3, 10**4, 10**5）とし、一貫性のある結果を受け取った

In [18]: import random 

In [57]: x = range(1000) 

In [58]: random.shuffle(x) 

In [59]: %timeit sorted(x) 
1000 loops, best of 3: 341 us per loop 

In [54]: x = range(1000) 

In [55]: random.shuffle(x) 

In [56]: %timeit sorted(x, reverse = True) 
1000 loops, best of 3: 344 us per loop 

。

Answer 3

私のベンチマークから、わずかな差があるように表示されます（私のマシン上）で

import timeit 

setup = """ 
import random 
random.seed(1) 
l = range(10000) 
random.shuffle(l) 
""" 

run1 = """ 
sorted(l) 
""" 

run2 = """ 
sorted(l, reverse=True) 
""" 

n1 = timeit.timeit(run1, setup, number=10000) 
n2 = timeit.timeit(run2, setup, number=10000) 

print n1, n2 
print (n2/n1 - 1)*100,"%" 

結果：

38.8531708717 41.2889549732 
6.26920286513 % 

同じ実行が、1000個の要素のリストについては：

2.80148005486 2.74061703682 
-2.17253083528 % 

# ...another round... 
2.90553498268 2.86594104767 
-1.36270722083 % 

Answer 4

驚くべきことに、リストを逆ソートするのに時間がかかります。他の答えはすでにこれを素晴らしいベンチマークで示しています。私はソースに見て、explanation in listobject.cが見つかりました：

/* Reverse sort stability achieved by initially reversing the list, 
applying a stable forward sort, then reversing the final result. */ 
if (reverse) { 
    if (keys != NULL) 
     reverse_slice(&keys[0], &keys[saved_ob_size]); 
    reverse_slice(&saved_ob_item[0], &saved_ob_item[saved_ob_size]); 
} 

だから、ソートされた出力を取得するには、リストはその後、並べ替えの前に逆転ソートし、最後に再び逆転されます。リストを逆にすると、O（n）の操作になるので、これ以上の支払いをするほどリストは長くなります。

これはとにかくカスタムキー機能を構築している場合は、あなたが直接それを否定することで、大きなリストのための時間を節約することができますことを示唆している：

very_long_list.sort(key=lambda x, y: -cmp(x, y)) 

代わりreversed=Trueを使用する：

very_long_list.sort(key=lambda x, y: cmp(x, y), reverse=True) 

この場合、もちろん、key=cmpを直接2番目のケースで渡すことができるので、ラムダ関数を介して余分な呼び出しを保存します。しかし、あなたがより大きな表現をしているなら、これはうまくいくかもしれません。list.sortからcmp引数とsorted組み込み関数はPython 2にXを非推奨となり、もはやあなたが気づいているように、なぜなら彼らは与えるパフォーマンスの低下、3 Xに許可されていることを

Answer 5

注意。代わりに、key引数を使用してカスタム並べ替え順序を定義する必要があります。