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

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有关列表的此属性).我需要保留元素的顺序.AFAIK有两种可行的方法

方法1:将B转换为集合并使用列表解析来生成C:

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

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

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

为什么#1效率更高#2？是否有转换为集合的开销？我在这里错过了什么？

本答案给出了一些性能基准.

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

Answer 1

有开销列表转换为一组,而是一组是显着比那些名单更快in的测试.

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

增加的速度可以抵消设置的创建开销,这就是您的设置检查最终更快的方式.

编辑:要回答其他问题,Python无法确定您的列表是否已排序 - list无论如何您都使用标准对象.因此,使用列表理解无法实现O(log n)性能.如果你想编写自己的二进制搜索方法,假设列表已经排序,你当然可以这样做,但O(1)任何一天都会击败O(log n).

Answer 2

集合中查找的平均时间复杂度(S中的x)是O(1),而列表中的相同是O(n).

您可以访问https://wiki.python.org/moin/TimeComplexity查看详细信息

Answer 3

根据关于时间复杂度的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)时间复杂度.