파이썬에서 중복을 확인하는 가장 빠른 방법은 무엇입니까?

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 

그럼에도 불구하고, 당신은 가독성을 위해 세트를 사용해야합니다.

물론 질문이 의미하는 것처럼, 우리는 해시 가능 유형에 대해 이야기하고 있습니다. 컨테이너처럼 unhashable 유형은 다른 기술을 필요로합니다. 완성도를 위해서

, 여기에 다른 수정 방법의 벤치 마크 :

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