7

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

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 函数实际上返回了相似之处。现在应该是正确的。

4

5 回答 5

8

仅从算法的角度来看，它需要O(n)构造集合并O(n)进行列表理解（因为测试一个元素是否包含在集合中是O(1)）。但是在第二个示例中，需要O(n^2)遍历两个列表。因此，无论使用哪种编程语言，第一种方法都更胜一筹。

此外，python 中的列表推导本质上比 for 循环更快。这进一步降低了常数因子（并且也显着降低了）。原因可以在我在这里引用的这篇文章中进行总结：

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

于 2012-05-09T17:20:30.910 回答
5

这两个选项之间的主要区别在于，使用的选项set渐近效率更高。

在相当有利的条件下，可以及时查找集合中的一个项目O(1)；在列表中查找项目需要O(n)时间。

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

于 2012-05-09T17:19:50.240 回答
2

在创建列表时，列表理解通常被认为比使用常规列表操作更有效。如果内存是一个问题，您可能想要使用生成器来代替。

这提供了一些关于for-loopsmap和list comprehension. @benhoyt 还提供了一个有用的链接，比较循环与列表理解。

但是，请注意，如果性能是一个特定问题，可能值得您花时间/基准测试您的各种选项，以便为您的特定要求选择最佳选项。

于 2012-05-09T17:17:46.200 回答
2

使用集合通常更快，因为它只需要迭代b一次，而您的示例必须b为a.

于 2012-05-09T17:19:25.013 回答
2

我做了一些测试：

test_lists.py

a = range(1, 1000)
b = range(2, 1002)

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

test_set_list_comprehensions.py

a = range(1, 1000)
b = range(2, 1002)

b = set(b)
[aa for aa in a if aa not in b]

测试集.py

a = range(1, 1000)
b = range(2, 1002)
list(set(a).difference(set(b)))

这就是 timeit 所说的：

~$ python -m timeit 'import test_lists'
1000000 loops, best of 3: 0.671 usec per loop
~$ python -m timeit 'import test_set_list_comprehension'
1000000 loops, best of 3: 0.766 usec per loop
~$ python -m timeit 'import test_set'
1000000 loops, best of 3: 0.656 usec per loop

所以最好的似乎是：

测试集.py

a = range(1, 1000)
b = range(2, 1002)
list(set(a).difference(set(b)))
于 2012-05-10T11:21:53.177 回答