为什么使用集合进行列表比较？

Question

我只是在寻找计算两个列表中的差异的方法时阅读了另一个用户问题.

Python,计算列表差异

我的问题是我为什么要这样做

def diff(a,b):
    b = set(b)
    return [aa for aa in a if aa not in b]

而不是做

def diff(a,b):
    tmp = []
    for i in a:
        if(i not in b):
            tmp.append(i)
return tmp

编辑:刚注意到第二个diff函数实际上返回了相似之处.现在应该是正确的.

Answer 1

从算法的角度来看,需要O(n)构造集合并O(n)进行列表理解(因为测试一个元素是否包含在集合中O(1)).但是在第二个示例中,需要O(n^2)遍历两个列表.因此,无论编程语言如何,第一种方法都是优越的.

此外,python中的列表推导本身比for循环更快.这进一步降低了常数因子(并且也显着降低).我在这里引用的帖子可以归纳为什么:

列表推导只能由表达式而不是语句组成这一事实是一个相当重要的因素,因为每次迭代的幕后需要的工作量要少得多.另一个因素是列表推导的基础迭代机制比执行for循环更接近C循环.

Answer 2

两个选项之间的主要区别在于使用的选项set渐近更有效.

在合理有利的条件下,可以及时查看集合中的项目O(1); 查找列表中的项目需要O(n)时间.

第二个不太重要的区别是,一个版本使用列表解析而另一个版本使用for循环.列表推导倾向于产生更紧凑的代码.它们也往往更有效(尽管如果性能是一个问题,获得准确图片的唯一方法是运行基准测试).