だから私は85項目のリストを持っています。このリストを継続的に半分に減らしたいと思っています (基本的にはアイテムのバイナリ検索です)。私の質問は、リストを減らす最も効率的な方法は何ですか? リスト内包表記は、理想的ではないリストのコピーを継続的に作成します。1 つの要素が残るまで、リストの範囲をその場で削除したいと考えています。
これが関連しているかどうかはわかりませんが、標準のリストの代わりに collections.deque を使用しています。おそらく多かれ少なかれ同じように機能するので、これが問題になるとは思えません。
わずか 85 項目の場合、正直なところ、使用したいほとんどすべての方法で十分な速度が得られます。時期尚早に最適化しないでください。
とはいえ、実際に何をしているかによっては、 alistは a よりも速い場合がありdequeます。Adequeはどちらかの端でアイテムを追加および削除するのに高速ですが、スライスはサポートされていません。
リストを使用して、連続する範囲のアイテム (たとえば最初の 42 個) をコピーまたは削除する場合は、スライスを使用してこれを行うことができます。各パスでリストの半分が削除されると仮定すると、アイテムを新しいリストにコピーするのは、既存のリストからアイテムを削除するよりも平均して遅くなります (削除するには、削除されていないリストの半分をメモリ内で「左方向」に移動する必要があります。残りの半分をコピーするのとほぼ同じ時間コストがかかりますが、常にこれを行う必要はありません; リストの後半を削除しても何も移動する必要はありません)。
これをdeque効率的に行うにはpop()、popleft()アイテムをスライスするのではなく (多数の属性アクセスとメソッド呼び出しがあり、Python では比較的コストがかかります)、操作を制御するループを Python で記述する必要があります。これは、ネイティブのスライス操作よりも遅くなります。
基本的にバイナリ検索だとおっしゃっていたので、元のコンテナをまったく変更せずに保持したいアイテムを見つけて、その単一のアイテムを保持する新しいコンテナを返すのがおそらく最も速いでしょう。インデックスによってアイテムに多くのアクセスを行うためlist、これは a よりも高速になります。dequea でこれを行うにはdeque、アイテムにアクセスするたびに Python がリンクされたリストを最初からたどる必要がありますが、インデックスによるアイテムへのアクセスは a の単純で高速な計算ですlist。
これが本当に必要なものかどうかはわかりませんが、次のようになります。
x = range(100)
while len(x) > 1:
if condition:
x = x[:int(len(x)/2)]
else:
x = x[int(len(x)/2):]
collections.dequeリンクされたリストを介して実装されるため、バイナリ検索は線形検索よりもはるかに遅くなります。アプローチを再考してください。
前の質問で、述語が与えられたアイテムのリストを削除するためのいくつかの手法を比較しました。(つまり、特定のアイテムを保持するかどうかについて True または False を返す関数があります。) 私が覚えているように、リスト内包表記を使用するのが最も高速でした。実際のところ、コピーは非常に安価です。
速度を改善するためにできる唯一のことは、削除するアイテムによって異なります。しかし、あなたはそれについて何も指摘していないので、私は何も提案できません。