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

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 更有效率呢？把列表转换成集合不是会有额外的开销吗？我是不是漏掉了什么？

一些性能基准测试可以在 这个回答中找到。

更新：我知道集合的平均查找时间是 O(1)，而列表是 O(n)，但如果原始列表 A 里有大约一百万个整数，创建集合的时间难道不会更长吗？

Answer 1

在一个集合中查找某个元素（比如看某个值x是否在集合S里）的平均时间复杂度是O(1)，而在一个列表中查找同样的元素，时间复杂度是O(n)。

你可以在这里查看详细信息：https://wiki.python.org/moin/TimeComplexity

Answer 2

根据Python关于时间复杂度的文档，我们可以了解到以下几点：

• 检查一个元素是否在列表中，比如用 x in s，平均来说是线性时间操作，也就是 O(n)。
• 检查一个元素是否在集合中，比如用 x in s，平均来说是常数时间操作，也就是 O(1)。

构建一个集合在最坏情况下是线性时间操作，因为你需要查看列表中的所有元素来建立一个哈希表，所以是 O(n)。这里的 n 是集合中元素的数量。

关键点在于，在方法1中，构建集合 s = set(B) 只需要做一次操作，之后我们只需要进行 n 次集合成员测试，比如 x not in B，所以总的时间复杂度是 O(n) + n * O(1)，也就是 O(n)。

而在方法2中，检查列表成员 x not in B 是对 A 中的每个元素都要进行的，所以总的时间复杂度是 n * O(n) = O(n^2)。

Answer 3

把一个列表转换成集合是有一些额外开销的，但集合在进行in测试时，比列表快得多。

你可以很快判断某个项目x是否在集合y中，因为集合底层使用了哈希表。无论你的集合有多大，查找的时间都是一样的（基本上是瞬间完成）——在大O表示法中，这被称为O(1)。而对于列表，你需要逐个检查每个元素，看看项目x是否在列表z中。随着列表的增大，检查所需的时间会变得更长——这就是O(n)，意味着操作的时间长度与列表的长度直接相关。

这种速度的提升可以抵消创建集合的开销，这就是为什么集合的检查会更快。

补充说明：为了回答另一个问题，Python无法判断你的列表是否是排序的——至少在使用标准的list对象时是这样的。所以它无法通过列表推导式实现O(log n)的性能。如果你想自己写一个假设列表是排序的二分查找方法，当然可以，但O(1)总是比O(log n)快。

补充说明2：

我知道集合的平均查找时间O(1)比列表的O(n)快，但如果原始列表A包含大约一百万个整数，创建集合的时间不会更长吗？

不会，完全不会。从列表创建集合是一个O(n)的操作，因为将一个项目插入集合是O(1)，而你要做这个操作n次。如果你有一个包含一百万个整数的列表，把它转换成集合涉及两个O(n)的步骤，而反复扫描列表会是n个O(n)的步骤。实际上，对于一个包含一百万个整数的列表，创建集合的速度大约会快250,000倍，而且随着列表中项目数量的增加，这个速度差距会越来越大。