Набор намного быстрее, чем список при поиске членства

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 использует хэширование (it allows only items which are hashable), которое будет намного быстрее, чем последовательный доступ list, для случайного поиска.

Но, 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 

Edit: Временная сложность различных операций на различных объектах задокументированы here. Спасибо @mgilson :)