1. Hironsan

    Posted

    Hironsan
Changes in title
+Pythonistaなら知らないと恥ずかしい計算量のはなし
Changes in tags
Changes in body
Source | HTML | Preview
@@ -0,0 +1,97 @@
+タイトルは煽り気味だけど知らなければ役にたつ話。
+
+最近久しぶりに[アルゴリズムイントロダクション](https://www.amazon.co.jp/dp/476490408X/)を読んでいるのですが、ふと「Python(CPython)のデータ構造に関する各操作の計算量ってどれくらいなのかな?」と気になったので調べてみました。以下のページを参考にしています:
+[Python Time Complexity](https://wiki.python.org/moin/TimeComplexity)
+
+以下では $n$ や $k$ といった記号を使います。ここで $n$ はコンテナ内の要素数、$k$ はパラメータ内の要素数かパラメータの値とします。では見ていきましょう。
+
+# リスト
+まずはリストです。Pythonではリストは内部的にはC言語の配列として表しているようです。そのため、要素の追加や削除を行うとそれ以降の要素をすべて移動する必要があるため大きなコストがかかります。なので先頭に要素を追加したり削除する必要がある場合は、代わりにcollections.dequeを使用することを推奨しています。
+
+| 操作 | 平均時評価 | 最悪時評価 |
+|---|---|---|
+|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](https://www.python.org/dev/peps/pep-3128/)
+
+# collections.deque
+ここでいう deque は内部的には双方向連結リストとして表されます。アルゴリズムの教科書によく出てくるアレですね。内部的に配列を使っているリストと比べてリストの両端に対する操作は高速ですが、中央部分に対する操作は相変わらず遅いです。
+
+| 操作 | 平均時評価 | 最悪時評価 |
+|---|---|---|
+|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演算が定数オーダーで可能なことから考えて、辞書と同様にハッシュテーブルを使っているのでしょう。
+
+| 操作 | 平均時評価 | 最悪時評価 |
+|---|---|---|
+|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) の方が少し速い。
+
+```py3
+for i in range(100):
+ s = set(range(1000000))
+ t = set(range(1000))
+ s.difference(t)
+ #s.difference_update(t)
+```
+
+# 辞書
+最後は辞書です。これはアルゴリズムの教科書ででてくるいわゆるハッシュテーブルと呼ばれるものです。ある要素の参照や削除が非常に高速に行えるのが特徴です。ただ、◯◯以下の要素を検索するというような処理には不向きなのでそういうときには2分探索木のようなデータ構造を使うのが良いでしょう。
+
+| 操作 | 平均時評価 | 最悪時評価 |
+|---|---|---|
+|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)$ |
+
+# おわりに
+アルゴリズムとデータ構造は非常に重要です。これがわかっていないと、長いリストに対して何度もin演算を行うコードを書くことになりかねません(よく見かけます)。行いたい処理によって適切なアルゴリズムとデータ構造を選択できるのがプロとして必要な要素なのではないでしょうか?
+
+そのために本記事が役に立てば幸いです。
+
+<!--
+[Cost of list functions in Python](http://stackoverflow.com/questions/1521784/cost-of-list-functions-in-python)
+-->