コンピュータのアーキテクチャについて、次の質問について考えました。Pythonで行うとします
from bisect import bisect
index = bisect(x, a) # O(log n) (also, shouldn't it be a standard list function?)
x.insert(index, a) # O(1) + memcpy()
にlog n加えて、私が正しく理解していれば、 のメモリコピー操作が必要x[index:]です。最近、ボトルネックは通常、プロセッサとメモリ間の通信にあるため、メモリのコピーはRAMによって非常に高速に実行できることを最近読みました。それはどのように機能しますか？
Pythonは言語です。複数の実装が存在し、リストの実装が異なる場合があります。したがって、実際の実装のコードを見ないと、リストがどのように実装され、特定の状況下でどのように動作するかを確実に知ることはできません。
私の賭けは、リスト内のオブジェクトへの参照が連続したメモリに格納されていることです（確かにリンクされたリストとしてではありません...）。その場合、挿入を使用x.insertすると、挿入された要素の後ろにあるすべての要素が移動されます。これはハードウェアによって効率的に行われる可能性がありますが、複雑さは依然としてO(n)です。
小さいリストの場合、前者がO(log n)で後者がO(n)bisectであっても、操作に より時間がかかる場合があります。ただし、リストが長い場合は、それがボトルネックであると推測する危険があります。このような場合、別のデータ構造の使用を検討する必要があります。x.insertx.insert
より優れた挿入パフォーマンスのリストが必要な場合は、 blist モジュールを使用してください。
CPython リストは連続した配列です。O(log n) bisect と O(n) insert のどちらがパフォーマンス プロファイルを支配するかは、リストのサイズと O() 内の定数要因によって異なります。特に、 bisect によって呼び出される比較関数は、リスト内のオブジェクトのタイプによっては高価なものになる可能性があります。
潜在的に大きな変更可能な並べ替えられたシーケンスを保持する必要がある場合、Python のリスト型の基礎となる線形配列は適切な選択ではありません。要件によっては、ヒープ、ツリー、またはスキップ リストが適切な場合があります。