Python中list、set与dict大规模数据查找效率实测对比

引言：对Python数据结构查找效率的常见误区

在日常开发中，我们经常需要执行元素的查找（find）或存在性判断（in）操作。过去我误以为Python的list内部实现了类似哈希或红黑树的结构，从而能高效支持查找。然而，通过实际测试list、set和dict在大规模数据下的查找性能后，才发现之前的认知存在严重偏差。

以下是具体的测试代码示例：

__author__ = 'jmh081701'
import numpy
import time
l=[]
sl=set()
dl=dict()
r=numpy.random.randint(0,10000000,100000)
for i in range(0,100000):
  l.append(r[i])
  sl.add(r[i])
  dl.setdefault(r[i],1)
#生成3种数据结构供查找，常规的list,集合sl,字典dl.里面的元素都是随机生成的，为什么要随机生成元素？这是防止某些结构对有序数据的偏向导致测试效果不客观。

start=time.clock()
for i in range(100000):
  t=i in sl
end=time.clock()
print("set:",end-start)
#计算通过set来查找的效率
start=time.clock()
for i in range(100000):
  t=i in dl
end=time.clock()
print("dict:",end-start)
#计算通过dict的效率
start=time.clock()
for i in range(100000):
  t=i in l
end=time.clock()
print("list:",end-start)
#计算通过list的效率

测试结果如下所示：

set: 0.01762632617301519
dict: 0.021149536796960248
······
···
··

令人惊讶的是，list在等待20分钟后仍未返回结果。

由此可见，各数据结构的性能差异一目了然。

综合查找效率排序为：set > dict > list。

时间复杂度深入解析：list、set与dict的差异

在单次查询场景中，list的查找复杂度确认为O(n)。set通过去重操作，其底层结构可能类似于红黑树（尽管Python具体实现可能不同，此处仅为推测，参考STL标准库），因此复杂度约为O(logn)。dict对key进行哈希处理后，再基于哈希值构建红黑树进行查找，其实际复杂度也是O(logn)，而非理论上理想的O(1)。所谓的O(1)仅存在于理想状态，实际哈希实现往往涉及离散化处理。由于dict比set多了一步哈希计算过程，因此其速度略慢于set，但差距并不显著。

结论：高频查找场景的最佳实践

因此，若业务场景涉及频繁的元素查找，强烈建议使用set。

以上就是本文的全部内容，希望对各位的学习有所帮助，也欢迎大家继续支持本站。