Pythonの組み込み型の操作の時間計算量を一覧で解説
Time complexity of operations on Python's built-in types
Python公式ドキュメントが、list、tuple、dict、set、str、bytes、bytearray、memoryview、rangeといった主要な組み込み型の各操作の時間計算量をBig O記法でまとめています。appendやget itemがO(1)である一方、insertやdeleteは位置によってO(n)になること、dictやsetの操作は平均O(1)だが最悪ケースではO(n)になることなど、実用的なパフォーマンス特性が一目でわかります。CPythonの実装に基づく情報で、他の実装では異なる可能性がある点も注記されています。
リストの最大のコストは、現在の割り当てサイズを超えて拡張するとき（すべてを移動する必要があるため）、または先頭付近で挿入や削除を行うとき（それ以降のすべてを移動する必要があるため）に発生します。
HNでの議論
42- alexpotato
Dave Beazley氏には、Pythonの組み込み型[0]をデータ分析やその他の高速な操作に使うことについての素晴らしい講演があります。
メタ的な注意として、私は長年にわたってこれらの組み込み型の多くを使ってきましたが、LLMのおかげで使う頻度が減ってきています。そのビデオをもう一度見ると、まるでブッシュクラフターがナイフとのこぎりだけで椅子を作るのを見ているかのようでした...
- Retr0id
素晴らしい。以前はこれはウィキで半ば非公式にしか文書化されていませんでした: https://wiki.python.org/moin/TimeComplexity
- StellarScience
Pythonは有名なことにハッシュテーブルを中心に構築されています。そのため、数バージョン前にハッシュテーブルの実装に改良が加えられ、言語全体が数パーセント速くなりました。
しかし、O(log(N))の複雑さを持つデータ構造がまったくないのを見て驚いています。確かにそれが望ましいユースケースもあるはずですが?
- mwkaufma
O(n - k)やO(len(l1) + len(l2))は単にO(n)ではありませんか? 複雑性解析とサイクルカウントの境界を曖昧にする代わりに、複雑性と推定される比例サイクルカウントを別々の指標として両方表示すればいいのでは?
- wodenokoto
なぜrangeオブジェクトの`min(r)`と`max(r)`がO(n)なのですか?
minとmaxはオブジェクトに格納された定数だと思っていました。基本的に、作成時に指定されたパラメータの1つを尋ねているだけです。