Python組み込み型の操作の時間計算量

組み込み型の操作の時間計算量 このページでは、CPythonにおける組み込み型の様々な操作の時間計算量について説明します。他のPython実装では異なるパフォーマンス特性を持つ場合があります。さらに、記載されているコストは厳密な組み込み型を想定しており、サブクラスのインスタンスでは異なるコストが発生する可能性があります。実行時間の増加が入力サイズに対してどのように成長するかを説明するために、Big O記法を使用します。特に断りのない限り、nはコンテナ内の要素数を表し、kはインデックスや繰り返し回数などの数値パラメータの値を表します。 list リストはミュータブルなシーケンスです。実装の詳細については、CPythonでリストはどのように実装されているかを参照してください。最大のコストは、現在の割り当てサイズを超えて成長する場合（すべてを移動する必要があるため）、または先頭付近での挿入または削除の場合（それ以降のすべてを移動する必要があるため）に発生します。両端での追加または削除が必要な場合は、代わりにcollections.dequeの使用を検討してください。 操作 複雑さ コピー (l.copy()) O(n) 追加 (l.append(x)) [1] O(1) ポップ (l.pop(k)) [1] [2] O(n - k) 挿入 (l.insert(k, x)) [1] [2] O(n - k) アイテム取得 (l[k]) O(1) アイテム設定 (l[k] = x) O(1) アイテム削除 (del l[k]) [2] O(n - k) イテレーション O(n) スライス取得 (l[i:j]) O(j - i) スライス設定 (l[i:j] = t) [1] O(j - i) len(t) == j - i の場合、それ以外は O(n - i + len(t)) スライス削除 (del l[i:j]) O(n - i) 拡張 (l.extend(t)) [1] [3] O(len(t)) ソート (l.sort()) [4] O(n log n) 連結 (l1 + l2) O(len(l1) + len(l2)) 乗算 (l * k) O(nk) x in l O(n) min(l), max(l) O(n) 長さ取得 (len(l)) [5] O(1) tuple タプルはイミュータブルなシーケンスです。タプルは決して変更できないため、挿入や削除のコストはなく、コピーを作成すると同じオブジェクトが返されるため、定数時間（O(1)）です。 操作 複雑さ コピー (tuple(t)) O(1) アイテム取得 (t[k]) O(1) スライス取得 (t[i:j]) O(j - i) 連結 (t1 + t2) O(len(t1) + len(t2)) 乗算 (t * k) O(nk) イテレーション O(n) x in t O(n) min(t), max(t) O(n) 長さ取得 (len(t)) [5] O(1) dict, frozendict dictオブジェクトに記載されている時間は平均ケースの時間です。これは、ハッシュ関数が衝突をまれにするのに十分に堅牢であると仮定しています。また、キーが可能なキーのセット全体に十分に分散されていると仮定しています。最悪の場合、すべてのキーが同じ値にハッシュされると、以下のO(1)操作はそれぞれO(n)の時間を要します。また、キーのハッシュ化と比較がO(1)であると仮定しています。実装の詳細については、CPythonで辞書はどのように実装されているかを参照してください。frozendictはイミュータブルであるため、アイテムの設定、削除、更新はサポートしていません。以下の他の操作は、同じコストで適用されます。 操作 複雑さ キー in d O(1) コピー (d.copy()) [6] [7] O(n) アイテム取得 (d[key], d.get(key)) O(1) アイテム設定 (d[key] = value) [1] O(1) アイテム削除 (del d[key], d.pop(key)) O(1) 更新 (d.update(t), d |= t) [1] [3] [7] O(len(t)) イテレーション [7] O(n) 長さ取得 (len(d)) [5] O(1) set, frozenset setとfrozensetの実装はdictと類似しており、同じ注意点が適用されます。最悪の場合、O(1)操作はO(n)の時間を要し、すべての要素を検索する操作はそれに応じて低下します。frozensetはイミュータブルであるため、追加、削除、またはインプレース更新操作はサポートしていません。以下の他の操作は、同じコストで適用されます。 操作 複雑さ x in s O(1) コピー (s.copy()) [6] [7] O(n) 追加 (s.add(x)) [1] O(1) 削除 (s.discard(x), s.remove(x)) O(1) 和集合 (s1 | s2, s1.union(s2)) [7] O(len(s1) + len(s2)) 更新 (s1 |= s2, s1.update(s2)) [1] [7] O(len(s2)) 積集合 (s1 & s2, s1.intersection(s2)) [7] [8] O(min(len(s1), len(s2))) 積集合更新 (s1 &= s2, s1.intersection_update(s2)) [1] [7] [8] O(min(len(s1), len(s2))) 差集合 (s1 - s2, s1.difference(s2)) [7] [9] O(len(s1)) 差集合更新 (s1 -= s2, s1.difference_update(s2)) [1] [7] [8] O(min(len(s1), len(s2))) 対称差集合 (s1 ^ s2, s1.symmetric_difference(s2)) [7] O(len(s1) + len(s2)) 対称差集合更新 (s1 ^= s2, s1.symmetric_difference_update(s2)) [1] [7] O(len(s2)) 長さ取得 (len(s)) [5] O(1) str, bytes, bytearray strとbytesオブジェクトは、それぞれ文字とバイトのイミュータブルなシーケンスです。タプルと同様に、コピーを作成すると元のオブジェクトが返されます。bytearrayはミュータブルであり、リストのミュータブル操作（sort()を除く）を同じコストでサポートします。ただし、先頭での削除（del (del b[0], del b[:k])）は、残りのバイトを移動する代わりにバッファの開始位置を進めるだけで、償却O(1)です。 操作 複雑さ アイテム取得 (s[k]) O(1) スライス取得 (s[i:j]) O(j - i) 連結 (s + t) [10] O(len(s) + len(t)) 乗算 (s * k) O(nk) 部分文字列検索 (x in s, s.find(x), s.index(x)) [11] O(n) 逆部分文字列検索 (s.rfind(x), s.rindex(x)) [11] [12] O(n × len(x)) エンコードまたはデコード [13] O(n) イテレーション O(n) 長さ取得 (len(s)) [5] O(1) memoryview memoryviewオブジェクトは、Pythonコードがコピーなしでバッファプロトコルをサポートするオブジェクトの内部データにアクセスできるようにします。特に、memoryviewのスライスは同じバッファへの新しいビューを返します。 操作 複雑さ 作成 (memoryview(obj)) O(1) アイテム取得 (v[k]) O(1) スライス取得 (v[i:j]) O(1) インデックス (v.index(x)) [11] [14] O(n) カウント (v.count(x)) [14] O(n) バイトへの変換 (v.tobytes(), bytes(v)) O(n) 長さ取得 (len(v)) [5] O(1) range rangeオブジェクトは、開始、停止、ステップの値からオンデマンドでアイテムを計算するため、ほとんどの操作は範囲の長さに依存しません。 操作 複雑さ アイテム取得 (r[k]) O(1) スライス取得 (r[i:j]) O(1) x in r [15] O(1) インデックスとカウント (r.index(x), r.count(x)) [15] O(1) イテレーション O(n) min(r), max(r) O(n) 長さ取得 (len(r)) [5] O(1) 注記