Pythonその2 Advent Calendar 2019の6日目です。昨日はbluepost59さんの内包表記を極めるでした。高速化のために有用な内包表記のパターンを網羅的に紹介されていました。

本記事も高速化を目的としています。より基本的な処理のパフォーマンスを整理するために、pythonのcollection型 (list/tuple/dictionary/set) の計算量を用途別にまとめたいと思います。

各collection型ごとに計算量をまとめてある記事は以下が詳しいです。

一方、用途ごとに色々なcollection型の計算量が一望できる記事はあまりなかったので違った角度で参考になるものが書ければなと思っています。

なお、CPython実装のPythonについて書きます。なので、PyPyなど別の実装に関しては参考にならない可能性があります。

計算量の表現記法

本記事では時間的計算量を$O$ 記法で表します。特に断らない限り平均時の計算量について議論することにします。また、本記事では$n$は対象となるcollection型の長さ、$k$は追加または削除などをするcollection型の長さを指すことにします。

記号	計算量	概要
$O(1)$	定数時間	処理速度はサイズに依らない
$O(n)$	線形時間	処理速度がサイズに1次比例する

ref: 計算量オーダーについて

検証環境

Python: 3.6.5
実行速度計測: jupyterのマジックコマンド (timeit)

用途一覧

長さの取得
値の参照
イテレーション
in演算子
値の代入
値の追加
値の削除

長さの取得

データ構造	計算量	記法
list/tuple	$O(1)$	len(seq)
dictionary	$O(1)$	len(dic)
set	$O(1)$	len(sets)

どのデータ構造でもサイズに依らず、同程度の処理の速さで長さを取得できます。
長さを計算しているわけではなく、長さ自体を格納しているので参照コストだけですみ、$O(1)$になっています。

値の参照

データ構造	計算量	記法
list/tuple	$O(1)$	seq[i]
	$O(k)$	seq[i:j]
dictionary	$O(1)$	dic[key]
set	$O(1)$	sets[i]

どのデータ構造でもサイズに依らず、同程度の処理の速さで値の参照ができます。
ただし、スライスは参照する範囲の長さには依ります

イテレーション

データ構造	計算量	記法
list/tuple	$O(n)$	for item in seq
dictionary	$O(n)$	for key in dic.keys()
	$O(n)$	for item in dic.values()
	$O(n)$	for key, item in dic.items()
set	$O(n)$	for item in sets

どのデータ構造でもサイズに依らず、同程度の処理の速さでイテレーションができます。

なお、計算量だけで言うとindexをイテレーションしてloopの中で値を参照するのと、表中に記載の処理は同じですが、実際は結構な速度差があるので表中のやり方でイテレーションするのがいいと思います。

def iter_index(seq:List[int], index:List[int]):
    """indexをイテレーションしてloop中で参照"""
    for idx in index:
        seq[idx]

seq = list(range(10000))
index = list(range(len(seq)))
%timeit iter_index(seq, index)
# >>> 281 µs ± 4.25 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

def iter_list(seq:List[int]):
    """collection型を直接イテレーション"""
    for item in seq:
        item
        
%timeit iter_list(seq)
# >>> 119 µs ± 2.08 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
# 2 ~ 3倍高速

in演算子

データ構造	計算量	記法
list/tuple	$O(n)$	item in seq
dictionary	$O(1)$	key in dic.keys()
	$O(n)$	item in dic.values()
	$O(1)$	(key, item) in dic.items()
set	$O(1)$	item in sets

直感的に分かると思いますが、list/tupleは$O(n)$です。また、dictionary.values()も$O(n)$です。
それ以外が$O(1)$なのは覚えておいて損はないと思います。これはdictionary型のkeyとset型がhash tableで実装されているためです。詳しくは以下の記事を参照して下さい。
ref: Pythonで"in list"から"in set"に変えただけで爆速になった件とその理由

「in set」の方が遅くなるケース

in演算子にはset型を使うのが高速ですが、実際はlist型の方が使用頻度が高いのでlist型をset型へ変換してからin演算子にわたすケースが多いのではないかと思います。変換のコストも考えると、いくつか注意が必要です。(以下listだけで調べますが、listではなくtupleでも同様な議論がなりたちます。)
「in list」, 「in set」, 「listからsetへの変換 & in set」を実測してみると、以下の様な結果がでました。

# 「in list」
lists = list(range(100000))
%timeit 50000 in lists
# >>> 622 µs ± 47.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

# 「in set」
sets = set(lists)
%timeit 50000 in sets
# >>> 54.8 ns ± 4.39 ns per loop (mean ± std. dev. of 7 runs, 10000000 loops each)

# 「listからsetへの変換 & in set」
%timeit 50000 in set(lists)
# >>> 2.94 ms ± 61.2 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

上記処理をサイズをかえて計測すると、

size	in set / in list 比	in set(list) / in list 比
10	3	4
100	19	3
1000	112	3
10000	1118	3
100000	11350	5

つまり、

「in set」は「in list」より高速。サイズが大きくなるほど線形に速度差は大きくなる
ただし、「listからsetへの変換 & in set」は「in list」より約3~5倍遅い

よって、以下のようなケースでは「in set」を使うことでかえって遅くなる可能性があります。

listからsetへの変換が必要
かつ、変換して作ったsetで「in set」を使う回数が5回程度より少ない

値の代入

データ構造	計算量	記法
list	$O(1)$	seq[i] = item
	$O(k)$	seq[i:j] = lists
dictionary	$O(1)$	dic[key] = item

代入は値の変更をし、長さをかえない操作を指すことにします。
setは値の変更はできず、削除して追加する必要があります。

値の追加

データ構造	計算量	記法	備考
list	$O(1)$	seq.append(item)	一番うしろに値を追加
	$O(n)$	seq.insert(item, i)	i番目に値を追加
	$O(k)$	seq.extend(list)	一番うしろにリストを結合
dictionary	$O(1)$	dic[key] = item	辞書に要素を追加
	$O(k)$	dic.update(dic2)	辞書の結合
set	$O(1)$	sets.add(item)	setに要素を追加

listはどこに値を追加するのかで計算量がかわってきます。できるだけ一番後ろに値を追加するようにアルゴリズムをくむべきだと思います。
また、上記の追加法はすべて破壊的（追加される前のものは残らない）なので変数のスコープに注意しないと思わぬ悪影響がでるかもしれません。

Pythonの配列は動的配列なので、確保している配列の容量を超えるとより大きな配列をつくり、そこに値をすべて移し替えます。そのさいの計算量は $O(n)$ です。しかし、空の状態からN回値を追加していった場合の平均計算時間 (ならし計算量という) が上表と同じオーダーになるそうです。
要素の追加回数が少なく、配列のサイズが非常に大きい場合は、ここでの内容と異なる振る舞いをする可能性があるので注意して下さい。

参考 - 計算量について、償却/期待/平均など

逐次追加 or 結合

追加する値を条件式でフィルターした末に決定する場合、以下の様に2通りの選択肢があります。

フィルターの最中に逐次的に値を追加する
フィルターで追加する値のcollection型を作った後にまとめて結合する

直感的には逐次的に追加するほうが無駄が少なそうですが、pythonではforが遅く、できるだけ内包表記を使ったほうがいいので微妙な問題です。試した結果を下記に記します。結果から言うと速度差はあまりなさそうです。便利な方を使っていいと思います。
個人的には、内包表記のほうが（値の代入・定義が少なくてすむため）副作用が少ない（はず）なので、後者のやり方の方がすきです。

追加する値のイテレーションが長い場合は内包表記で一旦リストをつくってからextendするほうが速そうです。
注.1) 破壊的追加をしてしまうと、サイズがかわってしまい、計測が不正確になるためリストをcopyして関数にわたします
注.2) appendは遅いことが知られているので変数に代入してから、loopの中で使います(参考: Pythonのリスト内包表記の速度)

def addition_extend(base:List[int], add:List[int]):
    add = [f for f in add if f]
    base.extend(add)
    return base

def addition_append(base:List[int], add:List[int]):
    base_a = base.append
    for ad in add:
        if ad:
            base_a(ad)
    return base

base = list(range(10000))
add = list(range(10))
%timeit addition_extend(copy(base), add)
# >>> 43.9 µs ± 6.94 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
%timeit addition_append(copy(base), add)
# >>> 39 µs ± 66.1 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

base = list(range(10))
add = list(range(10000))
%timeit addition_extend(copy(base), add)
# >>> 373 µs ± 45.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit addition_append(copy(base), add)
# >>> 540 µs ± 27.3 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

辞書

辞書についても同様に試しました。辞書は逐次代入のほうが速そうです。しかし、ゆらぎが大きいのでそこまで大差なさそうです。

def addition_update(base:Dict[str, int], add:Dict[str, int]):
    add = {f: g for f, g in add.items() if g}
    base.update(add)
    return base

def addition_assign(base:Dict[str, int], add:Dict[str, int]):
    for ad, val in add.items():
        if val:
            base[ad] = val
    return base

base = {str(f): f for f in range(10000)}
add = {str(f): f for f in range(10)}
%timeit addition_update(copy(base), add)
# >>> 365 µs ± 62.1 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit addition_assign(copy(base), add)
# >>> 312 µs ± 16.9 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)


base = {str(f): f for f in range(10)}
add = {str(f): f for f in range(10000)}
%timeit addition_update(copy(base), add)
# >>> 1.16 ms ± 35.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
%timeit addition_assign(copy(base), add)
# >>> 919 µs ± 45.5 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

値の削除

データ構造	計算量	記法	備考
list	$O(1)$	seq.pop()	一番うしろの値を削除
	$O(n)$	seq.delete(i), seq.pop(i)	値i/i番目の値を削除
dictionary	$O(1)$	dic.pop(key)	keyを指定して削除
set	$O(1)$	sets.discard(item)	値を指定して削除

~~リストは値の削除についても極力、一番うしろに限定したほうがいいです。~~

リストの要素の削除は、i番目の値を削除するとi+1番目以降の要素をすべて1つずつ手前にずらす処理が走ります。なので、削除する要素が最後尾に近ければ近いほど速いです。ここでの平均計算量はリストの中間に位置する要素の削除にかかる計算量を指します。

問題は削除する値が複数ある場合の処理です。直感的には削除する値が多くなってくると作り直したほうが速くなりそうです。この点に関して以下の2つ調べます。結果も先に書いておきます。

pop vs slice: sliceのほうがよさそう
delete vs 再作成: 再作成のほうがよさそう

pop vs slice

サイズnのリストをk回popすると$O(k)$、sliceすると$O(n-k)$です。ですが、単に、n > kならpop, n < kならsliceというわけにはいかないので、以下のコードで速度を測りました。

def pop(seq:List[int], num:int):
    for i in range(num):
        seq.pop()

def slices(seq:List[int], num:int):
    seq[:-num]

リストの長さと削除数をかえてpopとsliceの実行速度比を測った表が以下です。斜体部がsliceのほうが速かったケースです。基本的にはsliceの方がよさそうです。

pop / slice 比	削除数: 1	10	100	1000
list size: 10	1.2	3.0
100	1.0	1.6	10.9
1000	0.6	0.7	2.1	32.5
10000	0.6	0.5	0.5	1.7

delete vs 再作成

サイズnのリストをk回deleteすると$O(kn)$、再作成すると$O(n)$です。明らかに再作成したほうが速そうですが、以下のコードで速度を測ってみました。

def delete(lists:List[int], cond:Set[int]):
    for con in cond:
        try:
            lists.remove(con)
        except ValueError:
                pass
    return lists

def recreate(lists:List[int], cond:Set[int]):
    return [f for f in lists if f not in cond]

リストの長さと削除数をかえてdeleteとrecreateの実行速度比を測った表が以下です。斜体部がrecreateのほうが速かったケースです。基本的にはrecreateの方がよさそうです。

delete / recreate 比	削除数: 1	10	100	1000
list size: 10	0.7	1.5
100	0.3	1.3	3.5
1000	0.2	1.2	12.8	6.0
10000	0.3	1.8	114.7	117.4

まとめ

collection型の計算量を用途別にまとめました。pythonは処理が遅い言語だと言われていますが、少しでも許容可能な処理時間になるようにするための参考になれば幸いです！

明日は、typecprintさんです！