最近久しぶりにアルゴリズムイントロダクションを読んでいるのですが、ふと「Python(CPython)のデータ構造に関する各操作の計算量ってどれくらいなのかな？」と気になったので調べてみました。以下のページを参考にしています:
Python Time Complexity
以下では $n$ や $k$ といった記号を使います。ここで $n$ はコンテナ内の要素数、$k$ はパラメータ内の要素数かパラメータの値とします。では見ていきましょう。
2021/05/02
コメントでのご指摘を記事に反映しました。ありがとうございます。
リスト
まずはリストです。Pythonではリストは内部的にはC言語の配列として表しているようです。そのため、先頭要素の追加や削除を行うとそれ以降の要素をすべて移動する必要があるため大きなコストがかかります。なので先頭に要素を追加したり削除する必要がある場合は、代わりにcollections.dequeを使用することを推奨しています。
| 操作 | 平均計算量（Average Case） | ならし計算量（Amortized Worst Case） |
|---|---|---|
| Copy | $O(n)$ | $O(n)$ |
| Append | $O(1)$ | $O(1)$ |
| Insert | $O(n)$ | $O(n)$ |
| Get Item | $O(1)$ | $O(1)$ |
| Set Item | $O(1)$ | $O(1)$ |
| Delete Item | $O(n)$ | $O(n)$ |
| Iteration | $O(n)$ | $O(n)$ |
| Get Slice | $O(k)$ | $O(k)$ |
| Del Slice | $O(n)$ | $O(n)$ |
| Set Slice | $O(k+n)$ | $O(k+n)$ |
| Extend | $O(k)$ | $O(k)$ |
| Sort | $O(n \log n)$ | $O(n \log n)$ |
| Multiply | $O(nk)$ | $O(nk)$ |
| x in s | $O(n)$ | |
| min(s), max(s) | $O(n)$ | |
| Get Length | $O(1)$ | $O(1)$ |
Multiplyというのはリストに対する積のことですね。例えば、[0]*3みたいな。
ちなみに現在のリストをより高速なリストに置き換える提案もされていたようですが却下されています。pipからインストールして使うことはできます。
PEP 3128 -- BList: A Faster List-like Type
collections.deque
ここでいう deque は内部的には双方向連結リストとして表されます。アルゴリズムの教科書によく出てくるアレですね。内部的に配列を使っているリストと比べてリストの両端に対する操作は高速ですが、中央部分に対する操作は相変わらず遅いです。
| 操作 | 平均計算量（Average Case） | ならし計算量（Amortized Worst Case） |
|---|---|---|
| Copy | $O(n)$ | $O(n)$ |
| append | $O(1)$ | $O(1)$ |
| appendleft | $O(1)$ | $O(1)$ |
| pop | $O(1)$ | $O(1)$ |
| popleft | $O(1)$ | $O(1)$ |
| extend | $O(k)$ | $O(k)$ |
| extendleft | $O(k)$ | $O(k)$ |
| rotate | $O(k)$ | $O(k)$ |
| remove | $O(n)$ | $O(n)$ |
set
setは集合型のことですが、内部的な実装は辞書に非常に似ているようです。in演算が定数オーダーで可能なことから考えて、辞書と同様にハッシュテーブルを使っているのでしょう。
| 操作 | 平均計算量（Average Case） | 最悪計算量（Worst Case） |
|---|---|---|
| x in s | $O(1)$ | $O(n)$ |
| Union s or t | $O(len(s)+len(t))$ | |
| Intersection s&t | $O(\min(len(s), len(t))$ | $O(len(s) * len(t))$ |
| Multiple intersection $s_1$&$s_2$&..&$s_n$ | $(n-1)*O(l)$ ここで $l$ は$\max(len(s_1),..,len(s_n))$ | |
| Difference s-t | $O(len(s))$ | |
| s.difference_update(t) | $O(len(t))$ | |
| Symmetric Difference s^t | $O(len(s))$ | $O(len(s) * len(t))$ |
| s.symmetric_difference_update(t) | $O(len(t))$ | $O(len(t) * len(s))$ |
ここで気になったのは、difference と difference_update の平均計算量が違う点。difference は $ O(len(s))$ なのにdifference_update は $O(len(t))$ になっています。
これはどうもdifference は $s$ の各要素が $t$ に含まれていない場合に新しい集合に追加されるのに対して、difference_update は $t$ のすべての要素に対して $s$ から削除する操作を行うことに起因するようです。 したがって、集合の要素数の違いと新しい集合が必要か否かによって、どちらが良いのか選ぶ必要があります。
こんな感じで計測してみると、確かにこの場合は s.difference_update(t) の方が少し速い。
for i in range(100):
s = set(range(1000000))
t = set(range(1000))
s.difference(t)
#s.difference_update(t)
辞書
最後は辞書です。これはアルゴリズムの教科書ででてくるいわゆるハッシュテーブルと呼ばれるものです。ある要素の参照や削除が非常に高速に行えるのが特徴です。ただ、◯◯以下の要素を検索するというような処理には不向きなのでそういうときには2分探索木のようなデータ構造を使うのが良いでしょう。
| 操作 | 平均計算量（Average Case） | ならし計算量（Amortized Worst Case） |
|---|---|---|
| Copy | $O(n)$ | $O(n)$ |
| Get Item | $O(1)$ | $O(n)$ |
| Set Item | $O(1)$ | $O(n)$ |
| Delete Item | $O(1)$ | $O(n)$ |
| Iteration | $O(n)$ | $O(n)$ |