Python中集合与列表的in运算速度差异及相关设计疑问

问题1解答 #

• 两者底层数据结构差异导致时间复杂度完全不同：
  • 列表是顺序存储的动态数组，in 运算符执行时会从第一个元素开始逐个比对，直到找到匹配元素或者遍历完整个列表，平均时间复杂度为O(n)，列表越长、要找的元素越靠后/不存在，执行速度就越慢。
  • 集合基于哈希表（散列表）实现，in 执行时会先计算目标元素的哈希值，直接定位到元素对应的存储位置做少量比对即可得到结果，平均时间复杂度为O(1)，查询速度几乎不受集合大小影响。

问题2解答 #

• 这个优化思路不可能被原生实现，核心原因有3个：
  1. 单次查询场景下开销反而更高：把列表转成集合本身需要遍历整个列表完成哈希计算、写入哈希表的操作，时间复杂度本身就是O(n)，如果只对列表做1次in查询，转集合的额外开销会让整体速度比直接遍历列表更慢，只有在对同一个列表做多次in查询的场景下，提前转集合才有收益。
  2. 破坏列表现有语义兼容性：列表支持存储不可哈希的元素（比如嵌套的列表、未实现__hash__方法的自定义类实例），这类元素根本无法存入集合，要是原生把列表in改成转集合的逻辑，会导致大量现有合法代码直接报错。而且列表是有序、允许重复元素的，集合是无序、自动去重的，两者的设计定位完全不同，不能为了单一操作的优化破坏基础语义。
  3. 小列表场景性能反而下降：如果列表本身长度很小（比如只有几个到几十个元素），直接遍历的速度远高于转哈希表的开销，强行优化反而会让绝大多数小列表的in操作变慢。

内容的提问来源于stack exchange，提问作者s7eqx9f74nc4