【python】in演算子は遅いのか？

記事の概要

　素朴な疑問：

「in演算子は遅いのか？」

　速度を実測して検証しました。

記事の概要
はじめに
検証
結果
結論

はじめに

　inの速度は謎である。とりあえず、なんとなく速くはないイメージはあるといえばあるので、ループの中でinを書くとちょっと罪悪感のようなものを感じる。

　が、実際のところどうなのだろう？

　こちらのページに計算量は出ている。

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

　それによると、リストに対するinは平均O(n)で最悪はよくわからない。setに対するinは平均O(1)、最悪O(n)。

　つまりリストに対してin演算子を使うと線形探索される。一方、setはhashで実装されていると主張している。まあ、頷ける話ではある。

　とはいえ、計算量だけわかってもしょうがない。なので実測することにした。

検証

　次のようなベンチマークを考えた。

range(n)の値を持つコレクションを作り、range(2*n)の値に対してin演算子を実行。トータルの実行時間を測る。

　対象にしたコレクション型はlist, set, dict（dictのkey）の3通り。nは100, 200, 400, 600, 800, 1000, 2000, 4000, 6000, 8000, 10000。CPUはintel i7 3540Mで、プログラムはwindows上で動くvmware playerの仮想環境上のubuntuで実行。python 3.5.1。

　コードを以下に示す。

# coding: UTF-8

import time

import pandas as pd
import matplotlib.pyplot as plt

def measure(n, mode):
    if mode == "list":
        collection = list(range(n))
    elif mode == "set":
        collection = set(range(n))
    elif mode == "dkey":
        collection = dict(zip(range(n), range(n)))
    else:
        return None
        
    # measure overhead of for
    t1 = time.time()
    for i in range(2*n):
        pass
    t2 = time.time()
    overhead = t2 - t1

    t1 = time.time()
    for i in range(2*n):
        i in collection
    t2 = time.time()
    
    return t2 - t1 - overhead

def main():
    df = pd.DataFrame([], columns=["n", "list_time",
                                   "set_time", "dict_key_time"])
    for n in [100, 200, 400, 600, 800,
              1000, 2000, 4000, 6000, 8000,
              10000]:
        list_time = measure(n, "list")
        set_time = measure(n, "set")
        dkey_time = measure(n, "dkey")
        s = pd.Series([n, list_time, set_time, dkey_time],
                      index=df.columns)
        df = df.append(s, ignore_index=True)
    print(df)
    
    df.plot.line(x=["n"])
    plt.savefig("result.png")
    plt.yscale('log')
    plt.savefig("result_log.png")
    
if __name__ == "__main__":
    main()

結果

　プログラムのテキスト出力を以下に示す。

          n  list_time  set_time  dict_key_time
0     100.0   0.000230  0.000004       0.000004
1     200.0   0.000949  0.000008       0.000008
2     400.0   0.003813  0.000044       0.000018
3     600.0   0.008644  0.000030       0.000031
4     800.0   0.015412  0.000040       0.000040
5    1000.0   0.024412  0.000055       0.000068
6    2000.0   0.097047  0.000107       0.000109
7    4000.0   0.402630  0.000255       0.000235
8    6000.0   0.882451  0.000401       0.000443
9    8000.0   1.565103  0.000492       0.000473
10  10000.0   2.448165  0.000576       0.000587

　結果のグラフを次の図に示す。

　とりあえず、listが劇的に遅い。しかも、リストの大きさに比例するどころか、二次関数みたいな感じになっている（縦軸logの図を見る限り指数関数よりはマシ）。CPUキャッシュなどの影響だと思う。

　set, dictのkeyは互角の速度で、listと比べるといかなる要素数においても劇的に速い。1万要素（in演算2万回）で0.000612秒。O(n)と言えるかどうかはぶっちゃけ微妙。hashは衝突回避処理があるので、それが走ると遅くなるのだろうか。それともこれもキャッシュ関係？

結論

　listに対するin演算は激遅だった。これは大きいリストに対しては使いたくないと思う。

　set, dictのkeyに対するin演算は割と許せる速度なので、使うならこっち。だいたいリストの1/100～1/1000の速度が期待できる。リストでinすると15分かかる処理も1～10秒程度でできるということであり、つまり素晴らしい効能がある。

listに対してたくさん呼ぶのは地獄
in演算は無条件で遅い訳ではない。むしろsetなどに対してはそうとう速いので、基本的に使っても大丈夫

　これが結論である。なんだか、実際の数字が線形より悪かったり、組み込みのsetが優秀だったりっていうのは、少し意外な感じだった。

静かなる名辞

pythonとプログラミングのこと

【python】in演算子は遅いのか？

記事の概要

はじめに

検証

結果

結論