リストに要素を追加して順序を保持することは可能です

Question

リストの順序を保持する要素をリストに追加したいと思います。

のは、オブジェクトのリストがであると仮定しましょう[、B、C、D]私は、リストの2つの要素を比較する関数CMPを持っています。もし私がそれが最後の位置にあることを望むより大きいfオブジェクトを加えるならば。

多分完全なリストをソートする方が良いでしょう...

Answer 1

bisect.insort少し速くなり、該当する場合は、より追加-その後、ソート（あなたは再びソートするリストを必要とする前に追加するには、いくつかの要素を持っていない限り） - 私のラップトップ上でいつものように測定します（より高速なマシンはもちろん速く軒並みなりますが、比率は、ほぼ一定に保たなければならない）：あなたはこの気にどのくらい

$ python -mtimeit -s'import random, bisect; x=range(20)' 'y=list(x); y.append(22*random.random()); y.sort()' 
100000 loops, best of 3: 2.78 usec per loop 

対

$ python -mtimeit -s'import random, bisect; x=range(20)' 'y=list(x); bisect.insort(y, 22*random.random())' 
1000000 loops, best of 3: 1.99 usec per loop 

もちろん、この操作がアプリケーションにとってどれほど重大なボトルネックになっているかによって異なります。もちろん、マイクロ秒のこの部分でさえ違いはありますが、例外ではありますがルールではありません。

bisectモジュールはとして柔軟で構成することはできません - あなたは簡単に（あなたはおそらくキー=引数の形でそれを置くことができる場合は、強くを行うことをお勧めしているものの、ソートするために、独自のカスタムコンパレータを渡すことができますそれは、Pythonの3で、唯一=キーは、パフォーマンスがちょうど良い行うことができなかったため、CMPは、）、なくなっている=、まま、二等分厳格に使用しています内蔵の比較（あなたが__cmp__を実装するラッパーにあなたのオブジェクトをラップする必要があると思いますまたはあなたの好みに合わせて__le__を入力します。これには重要なパフォーマンスの影響もあります）。あなたの靴で

、私は追記その後、ソート・アプローチで始まり、およびプロファイリングは、パフォーマンスヒットが材料であることを示した場合にのみ、あまり便利な二分法に切り替えると思います。あまりにKnuth's（とホーアの）有名な引用、およびKent Beck'sほとんど-として有名なものを覚えている - ！）

Answer 2

はい、これは、しかし、それは比較関数を取ることはありません、ためbisect.insortが何であるかです。オブジェクトがカスタムオブジェクトの場合は、rich comparison methodsの1つ以上を上書きして、必要なソート順を設定できます。または、ソートキーを最初の項目として2タプルを格納し、代わりにソートすることもできます。

Answer 3

​​