检查python列表的最佳有效方式

Question

在上周的一次采访中，我被问到了这个问题，但我没有得到答案（无论如何都是正确的答案）。例如，你有列表A，它有以下元素[1,3,5,7,9,10]，然后你有列表B，它有如下元素：[3,4,5,6,7]，你想知道列表B中的哪些元素在列表A中。我的答案是：

for item in listA:
    for item1 in listB:
        if item1 == item:
            put item1 in some third list

但我知道这很糟糕，因为假设listA是一百万个元素，listB是十万个元素，这个解决方案就是垃圾。

在不重复两个列表的情况下，实现这样的目标的最佳方法是什么？

Answer 1

set(listA) & set(listB)是最简单的。

Answer 2

我建议将它们都转换为集合并进行交集：

setA = set(listA)
setB = set(listB)
setA.intersection(setB)

编辑：请注意，这将删除两个列表中的任何重复元素。因此，如果我们有listA = [1,1,2,2,3]和listB = [1,1,2,3]，那么交集将仅为set([1,2,3])。此外，对于最坏情况的估计，这将与列表理解-O(n * m)一样慢，其中n和m分别是列表的长度。然而，一般情况下的O(n) + O(m) + O(min(m,n)) == O(max(m,n))要好得多。

Answer 3

我也可以在混合中加入过滤器

filter(lambda x: x in listb,lista)

Answer 4

使用列表理解并使用in运算符测试成员资格：

[i for i in lista if i in listb]

将产生：

[3, 5, 7]

或者，可以使用集合运算，看看两个列表（转换为集合）的交集是什么

您可以使用集合（首选）：

listC = list(set(listA) & set(listB))

或者列表理解：

listC = [i for i in listA if i in listB]