회원 검색 동안 세트가 목록보다 훨씬 빠릅니다.

Question

목록에서 요소를 조회하는 것이 훨씬 빠르며, 목록의 정렬 된 유지 관리와 관련이 있습니까? 또는 조회 알고리즘이 목록과 다른 집합입니까?

>>> from timeit import Timer  
>>> Timer("100042 in L", "L=range(100000)").timeit(number=10000) 
21.69940710067749 
>>> 
>>> Timer("100042 in S", "S=set(range(100000))").timeit(number=10000) 
0.0006740093231201172 
>>> 

일부 링크는 두 링크 사이에 사용 된 링크 또는 알고리즘을 가리 킵니다.

Answer 1

set은 임의 검색을 위해 list의 순차 액세스보다 훨씬 빠른 해싱 (it allows only items which are hashable)을 사용합니다.

그러나 검색되는 항목이 처음 인 경우 list은 set을 초과 할 수 있습니다. 내 컴퓨터에

from timeit import Timer 
print Timer("0 in L", "L=range(100000)").timeit(number=10000) 
print Timer("0 in S", "S=set(range(100000))").timeit(number=10000) 

출력

0.00127078635541 
0.00143169642464 

편집 : 다양한 개체에 다른 작업 시간 복잡도는 here을 설명되어 있습니다. 감사합니다 @ mgilson :)