■集合に含まれているか探す [Python]

プロファイラを使うべきだけど横着。

1. ソート済みのlistを2分探索
2. ソートされていないlistのin演算子
3. dictのin演算子
4. dictのgetメソッド
5. setのin演算子

を調べた。
dictとsetのin演算子が速い。setの方がいつもちょっとだけ速い。dictを使うのはバッドノウハウで、意図通りのコードになるsetを使うべき。

import bisect
from datetime import datetime
import random


def index(a, x, l):
    """Locate the leftmost value exactly equal to x"""
    i = bisect.bisect_left(a, x)
    return i != l and a[i] == x

if __name__ == '__main__':
    SIZE = 10000
    i = [x * 2 for x in range(SIZE)]

    a = datetime.now()
    for idx in xrange(SIZE * 2):
        if index(i, idx, SIZE):
            pass
    b = datetime.now()
    print b - a

    random.shuffle(i)

    a = datetime.now()
    for idx in xrange(SIZE * 2):
        if idx in i:
            pass
    b = datetime.now()
    print b - a

    d = dict([(x, 1) for x in i])

    a = datetime.now()
    for idx in xrange(SIZE * 2):
        if idx in d:
            pass
    b = datetime.now()
    print b - a

    a = datetime.now()
    for idx in xrange(SIZE * 2):
        if d.get(idx):
            pass
    b = datetime.now()
    print b - a

    s = set(i)

    a = datetime.now()
    for idx in xrange(SIZE * 2):
        if idx in s:
            pass
    b = datetime.now()
    print b - a

0:00:00.022995
0:00:03.421239
0:00:00.002715
0:00:00.005084
0:00:00.002595

というメモ。