Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
511
Help us understand the problem. What is going on with this article?
@Hironsan

Pythonistaなら知らないと恥ずかしい計算量のはなし

タイトルは煽り気味だけど知っていると役にたつ話。

最近久しぶりにアルゴリズムイントロダクションを読んでいるのですが、ふと「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)$

参考資料

511
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Hironsan
あほぐらまー
tis
創業50年超のSIerです。

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
511
Help us understand the problem. What is going on with this article?