Pythonで重複をチェックする最も速い方法は何ですか？

Question

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

例えば：

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

なるセットを使用して（）同様に高速であるタイプ。 set（）では、愚かなNone値をハッシュキーに追加する必要はありません。

Answer 1

はい、セットを使用する必要があります。 （）同様に高速である入力セットを使用

---

なります。

いいえ、それほど高速ではありません。それは速くになります。一部の人々は、そのセットを示すベンチマークを掲載している

---

更新の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 

セット、少し速くなりました。

Answer 2

Dictsはわずかに速いですが、：

それでも

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]は最速ですが、何の関数呼び出しが関与していないので、この時間は、それは、何の驚きではありません。

Answer 3

辞書が高速であるようです。

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