組み込みの計算量¶

import なしで Python が提供するもの、すなわち組み込み型、組み込み関数、定数、そして例外の階層です。以下の各項目は、詳細な分析を載せたページにリンクしています。このページの表は主要な計算量を示しており、必要なものをひと目で見つけられます。

組み込み型¶

型	用途	平均アクセス	平均挿入	平均削除
`list`	順序付きのシーケンス	O(1)	O(n)	O(n)
`tuple`	不変のシーケンス	O(1)	-	-
`range`	数値のシーケンス	O(1)	-	-
`str`	テキスト	O(1)	-	-
`bytes`	バイナリデータ	O(1)	-	-
`dict`	キーと値の対応	O(1)	O(1)	O(1)
`set`	重複のない要素	-	O(1)	O(1)
`frozenset`	不変で重複のない要素	-	-	-

シーケンス型¶

リスト - もっとも柔軟なシーケンス型
タプル - 不変のシーケンス
範囲 - 遅延評価される数値シーケンス
文字列 - テキストと文字のシーケンス
バイト列とバイト配列 - バイナリデータと可変のバイト列

マッピング型と集合型¶

辞書 - ハッシュに基づくキーと値の格納
集合 - 順序を持たない重複のない要素
frozenset - 不変で重複のない要素

数値型と真偽値型¶

整数 - 任意精度の整数
浮動小数点数 - IEEE 754 倍精度
真偽値 - 2 つのシングルトン、int のサブクラス

組み込み関数¶

イテレーション¶

このグループの関数はイテレータを返します。生成自体は安価で、備考に挙げたコストは消費するときに支払うものです。

関数	時間	空間	備考
`iter()`	O(1)	O(1)	イテラブルをイテレータで包む
`next()`	O(1)*	O(1)	* コストは元になるイテレータ次第
`aiter()`	O(1)	O(1)	`iter()` の非同期版
`anext()`	O(1)	O(1)	await のコストは非同期ジェネレータのコストと同じ
`enumerate()`	O(1)	O(1)	消費に O(n)、`(index, item)` のタプルを生成
`zip()`	O(1)	O(1)	消費に O(n)、もっとも短いイテラブルで止まる
`map()`	O(1)	O(1)	消費に O(n*k)、k は関数の実行時間
`filter()`	O(1)	O(1)	消費に O(n*k)、k は述語の実行時間
`reversed()`	O(1)	O(1)	消費に O(n)、`__reversed__` か `__getitem__` が必要

集約と順序付け¶

関数	時間	空間	備考
`len()`	O(1)	O(1)	組み込みコンテナは長さをキャッシュしている
`sum()`	O(n)	O(1)	文字列の連結に誤用すると O(n²)
`min()`	O(n)	O(1)	すべての要素を比較する必要がある
`max()`	O(n)	O(1)	すべての要素を比較する必要がある
`sorted()`	O(n log n)	O(n)	Timsort（≤3.10）、Powersort（3.11+）
`all()`	O(n)	O(1)	最初の偽の要素で短絡する
`any()`	O(n)	O(1)	最初の真の要素で短絡する

数値と基数¶

関数	時間	空間	備考
`abs()`	O(1)	O(1)	独自の `__abs__()` では O(k)
`divmod()`	O(1)	O(1)	任意精度整数では O(n²)
`pow()`	O(log y)	O(1)	高速べき乗、3 引数形式は剰余のまま計算する
`round()`	O(1)	O(1)	ちょうど半分のときは銀行家の丸め
`bin()`	O(log n)	O(log n)	コストは出力の長さに等しい
`hex()`	O(log n)	O(log n)	コストは出力の長さに等しい
`oct()`	O(log n)	O(log n)	コストは出力の長さに等しい

テキストと文字¶

関数	時間	空間	備考
`chr()`	O(1)	O(1)	コードポイントから文字へ
`ord()`	O(1)	O(1)	文字からコードポイントへ
`format()`	O(n)	O(n)	n は結果の長さ
`repr()`	O(n)	O(n)	コンテナの中へ再帰する
`ascii()`	O(n)	O(n)	`repr()` と同様で、非 ASCII をエスケープする
`hash()`	O(k)	O(1)	文字列では O(n)、初回の呼び出し以降はキャッシュされる

オブジェクト、属性、型¶

関数	時間	空間	備考
`type()`	O(1)	O(1)	クラスを生成する 3 引数形式では O(n)
`isinstance()`	O(d)	O(1)	d は MRO の深さ、実際上は O(1)
`issubclass()`	O(d)	O(1)	d は MRO の深さ、実際上は O(1)
`callable()`	O(1)	O(1)	`__call__` の有無を調べる
`id()`	O(1)	O(1)	`is` 演算子の土台
`getattr()`	O(d)	O(1)	インスタンス辞書に当たれば平均 O(1)
`setattr()`	O(1)	O(1)	ハッシュテーブルへの挿入
`hasattr()`	O(d)	O(1)	`getattr()` と同じ探索で、例外を捕捉する
`delattr()`	O(1)	O(1)	ハッシュテーブルからの削除
`dir()`	O(n log n)	O(n)	結果のソートが支配的
`vars()`	O(1)	O(1)	`__dict__` への参照を返し、コピーはしない
`super()`	O(d)	O(d)	MRO をたどるが、MRO はキャッシュされている
`property()`	O(1)	O(1)	デスクリプタの生成とアクセス
`classmethod()`	O(1)	O(1)	デスクリプタの生成、探索は O(d)
`staticmethod()`	O(1)	O(1)	デスクリプタの生成、探索は O(d)

型のコンストラクタ¶

コンストラクタ	時間	空間	備考
`bool()`	O(1)	O(1)	コンテナは O(1) の `__len__()` で答える
`int()`	O(1)	O(1)	非常に長い数値文字列の解析では O(n²)
`float()`	O(1)	O(1)	文字列からは O(n)
`complex()`	O(1)	O(1)	文字列からは O(n)
`str()`	O(1)	O(1)	コンテナと独自の `__str__()` では O(n)
`bytes()`	O(n)	O(n)	n は元データの長さ
`bytearray()`	O(n)	O(n)	n は元データの長さ
`memoryview()`	O(1)	O(1)	バッファへのビューであり、コピーは作らない
`list()`	O(n)	O(n)	n はイテラブルの長さ
`tuple()`	O(n)	O(n)	引数がすでにタプルなら O(1)
`dict()`	O(n)	O(n)	ハッシュ衝突がある最悪の場合は O(n²)
`set()`	O(n)	O(n)	ハッシュ衝突がある最悪の場合は O(n²)
`frozenset()`	O(n)	O(n)	引数がすでに frozenset なら O(1)
`slice()`	O(1)	O(1)	添字を保持するだけで、適用には O(k) かかる
`object()`	O(1)	O(1)	すべてのクラスの基底

コードの実行¶

関数	時間	空間	備考
`eval()`	O(n + m)	O(n + m)	n はソースの長さ、m は評価のコスト
`exec()`	O(n + m)	O(n + m)	n はソースの長さ、m は実行のコスト
`compile()`	O(n)	O(n)	構文解析とバイトコード生成
`globals()`	O(1)	O(1)	既存のモジュール辞書を返す
`locals()`	O(1)	O(1)	最適化された関数スコープでは O(m)

入出力とデバッグ¶

関数	時間	空間	備考
`print()`	O(n)	O(n)	n は出力の総量、I/O が支配的
`input()`	O(k)	O(k)	k は読み込む行の長さ
`open()`	O(1)*	O(1)	* システムコール、読み書きは移動量に応じたコスト
`help()`	O(n)	O(n)	n は調べる対象の大きさ
`breakpoint()`	O(1)	O(1)	制御をデバッガに渡す

定数¶

定数	時間	空間	備考
`None`	O(1)	O(1)	シングルトン、`is` で比較する
`True`	O(1)	O(1)	シングルトンの `bool`
`False`	O(1)	O(1)	シングルトンの `bool`
`NotImplemented`	O(1)	O(1)	処理を辞退する演算子が返す
`Ellipsis`	O(1)	O(1)	`...` のシングルトン

例外とインタプリタ¶

例外 - 組み込み例外の階層と raise / catch のコスト
インタプリタ情報 - copyright、credits、license
Exit/Quit - exit と quit

重要な概念¶

償却計算量¶

list.append() のような一部の操作は償却 O(1) の計算量を持ちます。これは次のことを意味します。

ほとんどの append は O(1)
ときどきリサイズが起こり、そのときは O(n)
多数の操作を通してならすと、平均は O(1)

遅延評価と即時評価¶

いくつかの組み込み関数は、結果ではなくイテレータを返します。呼び出し自体は入力がどれだけ大きくても O(1) で、実際の処理はイテレータを消費するときに起こり、読み飛ばした要素についてはまったく起こりません。呼び出しを list() で包むと再び即時評価になり、O(n) の空間コストが戻ってきます。

実装の詳細¶

CPython は次のものを使っています。

リスト: 余分に確保する動的配列
辞書: オープンアドレス法のハッシュテーブル
集合: ハッシュテーブル（辞書とほぼ同じ）

バージョン別の注記¶

Python のバージョンによって最適化が異なります。

Python 3.7+: 辞書の挿入順序が保証される（言語仕様）
Python 3.9+: 新しい辞書実装による改善
Python 3.10+: よく使う操作へのさらなる最適化

リリースごとの詳しい変更履歴はバージョンを参照してください。