在查找成员资格时,Set比列表快得多

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顺序访问快得多,用于随机查找.

但是,如果被搜索的项目在开头,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

编辑:此处记录了各种对象上不同操作的时间复杂度.谢谢@mgilson :)