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

比如说，我想计算两个列表的差异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 and B都用唯一的整数排序（不确定是否有办法告诉Python列表的这个属性）。我需要保留元素的顺序。 AFAIK 有两种可能的方法

Method 1: 将 B 转换为集合并使用列表推导式生成 C：

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

Method 2: 直接使用列表理解：

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

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

一些性能基准给出在这个答案。

UPDATE:我知道一组的平均值O(1)查找时间胜过列表的查找时间O(n)但如果原始列表A包含大约一百万个左右的整数，集合的创建实际上不会花费更长的时间吗？

将列表转换为集合会产生开销，但集合是实质上比列表更快in tests.

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

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

编辑：为了回答另一个问题，Python 无法确定你的列表是否已排序 - 如果你使用的是标准则不行list无论如何，对象。因此它无法通过列表理解实现 O(log n) 性能。如果您想编写自己的二分搜索方法（假设列表已排序），您当然可以这样做，但 O(1) 随时都会击败 O(log n)。

EDIT 2:

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

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