python中不同数据结构的in操作效率

Question

我是编程新手，当我使用python时，我发现in操作在不同数据结构上的性能是完全不同的。例如：

a=list_a######list_a and list_b both are lists,data scale:300,000
b=set(list_b)
t1=time()
s=0
for entry in a:
    if entry in b:
        s+=1
t2=time()
print t2-t1

最后我得到了这样的结果，非常有效

0.0699999332428

但是，当我搜索列表\u b而不更改为设置数据结构时

a=list_a
b=list_b
t1=time()
s=0
for entry in a:
    if entry in b:
        s+=1
t2=time()
print t2-t1

而这一次结果花了将近十分钟

539.641000032

我在网上搜索了一下，发现这和hash-map有某种联系，但仍然很混乱。有人能详细解释一下吗？或者python中还有其他类似的数据结构吗？你知道吗

提前谢谢。你知道吗

Answer 1

列表具有线性时间查找。这是因为为了确定一个项目是否在列表中，Python需要扫描每一个项目，直到找到一个匹配的项目；因此所花费的时间与列表的长度成正比。单子越长，花的时间就越长。在计算机科学术语中，这被称为O(n)时间复杂性。你知道吗

集合和字典有固定的时间查找。它们不只是将元素存储在一个序列中，只按位置索引，而是存储值的散列。为了确定是否存在匹配项，Python对值进行哈希运算，然后转到匹配索引。不管集合有多大，它总是要花费相同的时间，这就是所谓的O(1)复杂性。你知道吗