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

このページでは、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]    | *O*(min(len(*s1*), len(*s2*)))                     |
| [8]                                                |                                                    |
+----------------------------------------------------+----------------------------------------------------+
| 共通集合による更新 ("s1 &= s2",                    | *O*(min(len(*s1*), len(*s2*)))                     |
| "s1.intersection_update(s2)") [1] [7] [8]          |                                                    |
+----------------------------------------------------+----------------------------------------------------+
| 差集合 ("s1 - s2", "s1.difference(s2)") [7] [9]    | *O*(len(*s1*))                                     |
+----------------------------------------------------+----------------------------------------------------+
| 差集合による更新 ("s1 -= s2",                      | *O*(min(len(*s1*), len(*s2*)))                     |
| "s1.difference_update(s2)") [1] [7] [8]            |                                                    |
+----------------------------------------------------+----------------------------------------------------+
| 対称差 ("s1 ^ s2", "s1.symmetric_difference(s2)")  | *O*(len(*s1*) + len(*s2*))                         |
| [7]                                                |                                                    |
+----------------------------------------------------+----------------------------------------------------+
| 対称差による更新 ("s1 ^= s2",                      | *O*(len(*s2*))                                     |
| "s1.symmetric_difference_update(s2)") [1] [7]      |                                                    |
+----------------------------------------------------+----------------------------------------------------+
| 長さの取得 ("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)",           | *O*(*n*)                                           |
| "s.index(x)") [11]                                 |                                                    |
+----------------------------------------------------+----------------------------------------------------+
| 逆方向の部分文字列の検索 ("s.rfind(x)",            | *O*(*n* × len(*x*))                                |
| "s.rindex(x)") [11] [12]                           |                                                    |
+----------------------------------------------------+----------------------------------------------------+
| エンコードまたはデコード [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)",        | *O*(1)                                             |
| "r.count(x)") [15]                                 |                                                    |
+----------------------------------------------------+----------------------------------------------------+
| イテレーション                                     | *O*(*n*)                                           |
+----------------------------------------------------+----------------------------------------------------+
| "min(r)", "max(r)"                                 | *O*(*n*)                                           |
+----------------------------------------------------+----------------------------------------------------+
| 長さの取得 ("len(r)") [5]                          | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+


注釈
====

[1] 償却計算量です。 内部の記憶領域のサイズを変更するときに、個々の操
    作が *O*(*n*) になることがありますが、コンテナに対してそれまでに行
    った操作に応じて、このコストは多数の操作に分散されます。

[2] 要素数 *n* のリストで、インデックス *k* の要素を取り出して削除する
    か、単に削除すると、*k* より後のすべての要素が 1 要素分ずつ左にず
    れ、*n* - *k* - 1 個の要素が移動します。 インデックス *k* に挿入す
    ると、*k* 以降の要素が 1 要素分ずつ右にずれ、*n* - *k* 個の要素が
    移動します。 最悪の場合はインデックスが 0 のときで、リストの残りの
    要素すべてを移動しなければなりません。 平均的な場合はリストの中央
    のインデックスで、*O*(*n*/2) = *O*(*n*) の操作が必要です。 リスト
    の末尾で操作する場合は何も移動せず、*O*(1) です。

[3] これに加えて、*t* をイテレートするコストがかかります。 任意のイテ
    ラブルでは、このコストが高くなる場合があります。

[4] これは最悪の場合です。 ソートは入力の状態に適応するため、すでにソ
    ート済み、または逆順にソート済みの入力では、比較は *O*(*n*) 回で済
    みます。 詳細については、Objects/listsort.txt を参照してください。

[5] 要素数はオブジェクトに格納されているため、"len()" が要素を数える必
    要はありません。

[6] "frozendict" または "frozenset" のコピーは元のオブジェクトを返すた
    め、*O*(1) です。

[7] These operations scan the container's internal hash table, which
    is not shrunk when elements are removed. After removing most
    elements, they still take time proportional to the container's
    former size, until a later insertion triggers a resize.

[8] *t* が集合型のオブジェクトでない場合は *O*(len(*t*)) です。

[9] *t* が集合型のオブジェクトでない場合は *O*(len(*s*) + len(*t*)) で
    す。

[10] 結合のたびに新しいオブジェクトが作成されるため、ループ内で多数の
     断片を結合して文字列を構築すると、実行時間は全体の長さの二乗に比
     例します。 ほかの方法については、不変のシーケンスの結合に関する注
     記 を参照してください。

[11] With *start* and *end* arguments, *n* is the length of the region
     searched rather than of *s*, and unlike slicing nothing is
     copied.

[12] これは最悪の場合です。 通常の入力では、逆方向の検索は *O*(*n*) で
     す。 一方、順方向の検索は、最悪の場合でも線形時間となる、より精巧
     なアルゴリズムを使います。 このアルゴリズムは
     Objects/stringlib/stringlib_find_two_way_notes.txt で説明していま
     す。

[13] 1 文字ごとに一定量の処理を行うコーデックを前提としています。

[14] これらの操作は各要素を個別にアンパックして比較するため、対応する
     "bytes" のメソッドよりはるかに遅くなります。

[15] 引数が "int" または "bool" であることを前提としています。 ほかの
     型の場合は、ほかのシーケンスと同様に、"range" オブジェクト内を
     *O*(*n*) の時間で検索します。
