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

このページでは、CPython の組み込み型に対するさまざまな操作の時間計算量を説明します。 ほかの Python 実装では、性能の特性が異なる場合があります。 また、サブクラスのインスタンスではコストが異なる場合があるため、ここに示すコストは組み込み型そのものを前提としています。

Big O notation を使って、入力のサイズに応じて操作の実行時間がどのように増加するかを説明します。 特に断りのない限り、n は現在コンテナに含まれる要素の数を表し、k はインデックスや繰り返し回数などの数値引数の値を表します。

list

Lists are mutable sequences; for more detail on the implementation see CPythonでリストはどのように実装されているのですか？. The largest costs come from growing beyond the current allocation size (because everything must move), or from inserting or deleting somewhere near the beginning (because everything after that must move). If you need to add or remove at both ends, consider using a collections.deque instead.

演算

計算量

コピー (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]

len(t) == j - i の場合は O(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

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 は不変なので、要素の設定、削除、更新をサポートしません。 以下のほかの操作は、同じコストで適用できます。

演算

計算量

key 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 は可変で、list の変更操作 (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(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 オブジェクトは、start、stop、step の値から必要に応じて要素を計算するため、ほとんどの操作は範囲の長さに依存しません。

演算

計算量

要素の取得 (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)

注釈