python - Pythonで重複をチェックする最速の方法は何ですか?

Question

辞書を使うのが理想的です。

例えば：

history = {}
for i in collection:
    if i not in history:
        history[i] = None
        # fancy computation here

set() タイプを使用しても同じくらい高速です。set() では、ばかげた None 値をハッシュ キーに追加する必要はありません。

Answer 1

はい、セットを使用する必要があります。

---

set() タイプを使用しても同じくらい高速です。

いいえ、それほど速くはありません。それはより速くなります。

---

アップデート

set が dict よりも遅いことを示すベンチマークを投稿した人もいます。セットが単純であることを除いて、基本的に同じ実装を持っているため、これは少し驚くべきことだと思います。遅い理由を見つけたと思います：

def set_way():
    my_set = set()
    my_set_add = my_set.add   # remember the method
    for ele in x:
        if ele not in my_set:
            my_set_add(ele)   # call the method directly

結果：

dict time : 1.896939858077399
set time : 1.8587076107880456

予想どおり、Set がわずかに速くなりました。

Answer 2

辞書の方が速いようです。

import timeit
import random as rn

x  = [rn.choice(xrange(10000)) for i in xrange(1000)]

def set_way():
    my_set = set()
    for ele in x:
        if ele in my_set:
            return True
        else:
            my_set.add(ele)
    else:
        return False

def dict_way():
    dicto = {}
    for ele in x:
        if ele in dicto:
            return True
        else:
            dicto[ele] = None
    else:
        return False



num = 10000

set_time = timeit.timeit(set_way, number = num)
print 'set time :', set_time
dict_time = timeit.timeit(dict_way, number = num)
print 'dict time :', dict_time

結果：

set time : 0.619757678699
dict time : 0.466664548148

Answer 3

dict はより高速ですが、ほんのわずかです。

import timeit

setup = """
x = range(10000)
s = set(range(5000))
d = dict.fromkeys(range(5000))
"""

print '# set', timeit.timeit('for i in x: z = i in s', setup, number=1000)
print '# dic', timeit.timeit('for i in x: z = i in d', setup, number=1000)

# set 1.18897795677
# dic 1.1489379406

ただし、パフォーマンスが絶対に重要でない限り、読みやすさのためにセットを使用する必要があります。

もちろん、あなたの質問が示唆するように、ハッシュ可能な型について話しているのです。コンテナのようなハッシュ不可能な型には、別のテクニックが必要です。

完全を期すために、さまざまな変更方法のベンチマークを次に示します。

import timeit

setup = """
x = range(10000)
s = set(range(5000))
d = dict.fromkeys(range(5000))

add_method = s.add
"""

print '# set-add     ', timeit.timeit('for i in x: s.add(i)', setup, number=1000)
print '# set-closure ', timeit.timeit('for i in x: add_method(i)', setup, number=1000)
print '# dict []     ', timeit.timeit('for i in x: d[i]=None', setup, number=1000)
print '# d.setdefault', timeit.timeit('for i in x: d.setdefault(i)', setup, number=1000)

# set-add      1.96829080582
# set-closure  1.2261030674
# dict []      0.982795000076
# d.setdefault 2.27355480194

dict[i]が最速ですが、関数呼び出しが含まれていないため、今回は驚くことではありません。