在 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

但是，当我搜索list_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

我搜索了互联网，发现这与哈希图有某种关系，但仍然令人困惑。任何人都可以详细解释一下，或者 python 中还有其他与此类似的数据结构吗？

提前谢谢。

Answer 1

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

集合和字典具有恒定的时间查找。它们不只是将元素存储在一个系列中，仅按位置索引，而是存储值的哈希值。为了查找是否存在匹配项，Python 对值进行哈希处理并转到匹配索引。无论集合有多大，它总是需要相同的时间 - 这被称为O(1)复杂性。