python - 为什么将列表转换为集合比仅使用列表来计算列表差异更快？

Question

比如说，我想计算两个列表C = A - B的差值:

A = [1,2,3,4,5,6,7,8,9] 
B = [1,3,5,8,9]
C = [2,4,6,7]          #Result

A 和 B 都用唯一的整数排序(不确定是否有办法告诉 Python 关于列表的这个属性)。我需要保留元素的顺序。据我所知，有两种可能的方法

方法一:将B转换为集合，使用列表推导生成C:

s = set(B)
C = [x for x in A if x not in s]

方法二:直接使用列表理解:

C = [x for x in A if x not in B]

为什么 #1 比 #2 更有效率？转换为集合没有开销吗？我在这里缺少什么？

一些性能基准在 this answer. 中给出

更新:我知道集合的平均 O(1) 查找时间优于列表的 O(n) 但是如果原始列表 A 包含大约一百万个整数，那么集合创建实际上不会花费更长的时间吗？

Answer 1

将列表转换为集合会产生开销，但对于那些in 测试，集合显着比列表快。

您可以立即查看项目 x 是否在集合 y 中，因为下面使用了一个哈希表。无论您的集合有多大，查找时间都是相同的(基本上是瞬时的)——这在大 O 表示法中称为 O(1)。对于列表，您必须单独检查每个元素以查看项目 x 是否在列表 z 中。随着列表的增长，检查将花费更长的时间 - 这是 O(n)，这意味着操作的长度与列表的长度直接相关。

提高的速度可以抵消设置创建开销，这就是您的设置检查最终变得更快的原因。

编辑:为了回答另一个问题，Python 无法确定您的列表是否已排序 - 无论如何，如果您使用的是标准 list 对象，则无法确定。所以它无法通过列表理解实现 O(log n) 性能。如果您想编写自己的假定列表已排序的二进制搜索方法，您当然可以这样做，但 O(1) 总比 O(log n) 好。

编辑 2:

I'm aware that a set's average O(1) lookup time beats that of a list's O(n) but if the original list A contains about a million or so integers, wouldn't the set creation actually take longer?

不，一点也不。从列表中创建一个集合是一个 O(n) 操作，因为将一个项目插入一个集合是 O(1) 并且您要执行 n 次。如果您有一个包含一百万个整数的列表，将其转换为一个集合需要两个 O(n) 步，而重复扫描该列表将是 n 个 O(n) 步。实际上，对于包含一百万个整数的列表，创建集合的速度大约要快 250,000 倍，并且列表中的项目越多，速度差异就会越来越大。