コンピュータのアーキテクチャに関する次の質問について考えました。私はそれを正しく理解すれば、log nをとり、プラスのPythonリストのパフォーマンス（...）。insert（...）
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()
、x[index:]ためのメモリコピー操作で行うとします。今私は最近ボトルネックはプロセッサとメモリの間の通信にあるので、メモリコピーはが非常に高速に処理できることを最近読んだ。それはどのように働くのですか？
Pythonは言語です。 Multiple implementations exist、およびはリストの実装が異なります。したがって、実際の実装のコードを見ることなく、リストがどのように実装され、特定の状況下でそれらがどのように動作するかを確実に知ることはできません。
私の考え方は、リスト内のオブジェクトへの参照が連続したメモリに格納されていることです（確かにリンクされたリストではありません...）。それが実際そうであれば、x.insertを使用して挿入すると、挿入された要素の背後にあるすべての要素が移動します。これはハードウェアによって効率的に行うことができますが、複雑さは依然としてO（n）です。小さいリストについて
後者はO（N）であるbisect動作（ログn）前者はOであっても、x.insertより多くの時間を取ることができます。しかし、長いリストの場合、私はx.insertがボトルネックだと推測する危険があります。そのような場合は、別のデータ構造の使用を検討する必要があります。
CPythonリストは連続した配列です。 O（log n）bisectとO（n）のどちらがあなたのパフォーマンスプロファイルを支配しているかは、あなたのリストのサイズとO（）内の定数要因によって決まります。特に、bisectによって呼び出される比較関数は、リスト内のオブジェクトのタイプに応じて高価になる可能性があります。
潜在的に大きな変更可能な並べ替えられたシーケンスを保持する必要がある場合は、Pythonsリストタイプの基になる線形配列は適切な選択肢ではありません。要件に応じて、ヒープ、ツリー、またはスキップリストが適切かもしれません。
挿入のパフォーマンスが向上するリストが必要な場合は、blist moduleを使用してください。
memcpy（）はO（1）だと言っているのではない - 私はO（n）だと分かっていますが、定数は小さくてもかまいません。しかし、もしそれが、あなたが純粋に考えるよりも1000倍速くなるように最適化されていれば、それはおそらく知る価値のあるものです。 –
場合によっては、リストにスペースが残っていない可能性があるので、memmove/memcpyの代わりに新しい空きメモリーが割り当てられた後にリスト全体をコピーする必要があります。 –
答えは有効ですが、最初の段落は一般的に必ずしも真ではありません。言語は、特定の状況下で効率的になるように設計された操作を指定することができるため、特定の実装のソースコードを見なくても、実装が適合していると仮定すると、それらの操作の特定のパフォーマンス特性を確信することができます。 – LarsH