比较两个列表中是否存在相同元素

Question

如何最简单、最优雅地检查一个元素是否存在于两个给定的列表中？例如，我有以下两个列表：

>>>a, b = ['a', 'b', 'g', 'r'], ['e', 'g', 'l', 1, 'w']

现在我想检查上述给定的列表中是否存在任何同时存在于两个列表中的元素。目前我的做法如下：

def elm_exists(list_a, list_b):
    for elm in list_a:
        if elm in list_b:
            return True
    return False

有更优雅的方法来做这件事吗？

- Amyth

---

每个列表中的元素是否唯一？如果是，您可以使用“集合”来轻松完成此操作。 - user849425

是的，列表中的元素是唯一的。 - Amyth

@Mike：等一下，即使元素不唯一，为什么你不能使用集合来完成这个任务呢？虽然你会失去一个元素出现多次的信息，但是如果你只关心元素是否存在，那么你并不需要这些信息。（而且，如果你确实需要这些信息，你可以使用Counter代替set来保留它。） - abarnert

Answer 1

使用以下方法检查a和b元素：

set(a).intersection(b)

例子：

In [44]: nk=set(a).intersection(b)

In [45]: for x in a:
    ...:     if x in nk:
    ...:         print x, 'present in b'
    ...:     else:
    ...:         print x, 'absent in b'
    ...:         
a absent in b
b absent in b
g present in b
r absent in b

此外：

In [47]: timeit(set(a) & set(b))
1000000 loops, best of 3: 940 ns per loop

In [48]: timeit(set(a).intersection(b))
1000000 loops, best of 3: 854 ns per loop

In [49]: timeit([x for x in a if x in b])
1000000 loops, best of 3: 1 us per loop

因此使用set(a).intersection(b)。

- namit

---

我不确定对于这么短的列表计时结果是否有太大意义。如果你只将长度减少到3和4而不是4和5，那么这足以使得list比较速度比任何一个set版本都要快，在我的电脑上至少是这样，但我并不认为这意味着使用O(NM)算法比O(N+M)更好！ - abarnert

看我的编辑答案。这取决于你的数据集的大小和碰撞的频率。这应该很明显...但直到我试图理解这些数字之前，我才意识到这一点。无论如何，在大多数情况下，这两个版本和我在set(a)上的生成器表达式都足够快，而OP最初的问题是关于优雅而不是性能的，所以...我认为intersection比&更优雅和可读，而any...in...for表达式则更加如此，但你的情况可能有所不同。 - abarnert

Answer 2

这个有效：

>>> l1,l2=['a', 'b', 'g', 'r'], ['e', 'g', 'l', 1, 'w']
>>> list(set(l1)&set(l2))
['g']

- the wolf

Answer 3

您不需要将两个list都转换为set，只需要转换其中一个。我认为跳过不必要的转换可以使代码更可读、更优美。

因此，可以选择以下任一方法：

set(a).intersection(b)

或者：

s = set(a)
any(e in s for e in b)

后者的优点在于发现一个匹配项后就立即短路，更好地表达逻辑，并返回True或False而不是非假或假的set，但如果这让您感到困扰，它将变成两行。我不知道这种优势是否抵消了将循环放在生成器表达式中而不是C函数内部的成本。 list大小如此小的性能结果几乎没有意义，因此让我们尝试一下：

In [373]: a=[random.choice(string.ascii_lowercase) for _ in range(10000)]
In [374]: b=[random.choice(string.ascii_lowercase) for _ in range(10000)]
In [375]: %timeit(set(a))
10000 loops, best of 3: 180 us per loop
In [376]: s=set(a) # since all versions need to do this
In [391]: %timeit(s & set(b))
1000000 loops, best of 3: 178 us per loop
In [392]: %timeit(s.intersection(b))
1000000 loops, best of 3: 247 us per loop
In [393]: %timeit(discard(e in s for e in b))
1000000 loops, best of 3: 550 ns per loop
In [394]: %timeit(any(e in s for e in b))
1000000 loops, best of 3: 749 ns per loop
In [395]: %timeit(any(e in a for e in b))
1000000 loops, best of 3: 1.42 us per loop

将所有数字转换为纳秒级别，加上除最后一个之外的set(a)成本，并比较来自三个Python版本的相同测试（Apple股票CPython 2.7.2、python.org CPython 3.3.0、Homebrew PyPy 1.9.0/2.7.2，所有64位Mac构建）：

                  CP272  CP330  PyPy
s & set(b)        358000 316000 180500
s.intersection(b) 427000 459000 180900
discard(genexp)   180550 157341  90094
any(genexp)       180749 157334  90208
any(list-genexp)    1420    686    960

现在我想起来了，这完全有道理。早期发生碰撞的几率非常高，因此将整个内容转换为集合的成本占主导地位。

这意味着我们需要一个新的测试，并且需要10000个唯一值。让我们用以下内容重复测试：

In [29]: a, b = list(range(10000)), list(range(10000))
In [30]: random.shuffle(a)
In [31]: random.shuffle(b)

                  CP272  CP330  PyPy
s & set(b)        1277000 1168000 1141000
s.intersection(b) 1165000 1117000 2520000
discard(genexp)   1699000 1271000  770000
any(genexp)        389800  344543  320807
any(list-genexp)    62000   10400    1520

以下更为合理，而且仍然有意义。如果你正在比较相同的10000个元素并进行随机洗牌，你需要进入每个元素多远？不够深入，使得将列表转换为set的成本不值得去做，更不用说两个列表都要转换了！

所以，让我们尝试一种没有匹配项的情况：

In [43]: a=list(range(10000, 20000))


                  CP272     CP330     PyPy
s & set(b)           751000    770000  733000
s.intersection(b)    466000    530000 1920000
discard(genexp)     1246000    985000  749000
any(genexp)         1269000    966000  893000
any(list-genexp)  185000000 176000000 5870000

我不知道PyPy如何如此快速地完成最后一个任务，但除此之外，没有什么惊喜的了。

那么，哪一个最好呢？

很明显，如果你预计会有很多冲突，你要尽可能地避免制作集合；但如果你预计会有少量冲突，你至少要制作一个集合。如果你没有头绪，我认为最安全的选择是any(genexp)——最坏情况下它比最佳情况差不到3倍，如果冲突率很高，它会快得多。但你可以看看数字并自行判断。

或者，更好的方法，当然是将它们与你预期遇到的真实测试数据进行比较。

- abarnert

---

干得不错（加1），但是OP要求的是“最简单”和“最优雅”的，而不是最快的！作为一个Numpy用户，我首先想到的函数是np.any(np.in1d(x, y))。我很好奇它与其他方法的比较结果。然而，你的证据支持了一个普遍规律...转换数据的成本通常超过了测试的成本，除非数据集非常大。 - cxrodgers

@cxrodgers：我的回答开始是关于“可读性”和“优雅性”的，这就是原始版本中的全部内容，我认为这仍然是回答中最重要的部分。所有其他东西都是在不可避免的关于什么最快的争论之后添加的；它比重要部分长得多的唯一原因是你可以保持简单，但你不能保持性能测试简单。 - abarnert

Answer 4

def elm_exists(lista, listb):
    return bool(set(lista) & set(listb))

bool函数对于所有非空容器返回True，对于空容器返回False。集合的交集（&）将返回两个集合中共有的元素集合。请注意，集合将删除任何重复项。

另外，您可以在bool函数中使用set(lista).intersection(listb)。

- Volatility

---

在交集中使用的 set(listb) 是多余的，因为 .intersection 可以接受任何可迭代对象作为参数。 - Jon Clements

此外，您在这里不需要使用len，因为bool(len(x))保证会返回与bool(x)相同的结果，而且更加简单和高效。 - abarnert

感谢JonClements和abarnert的帮助，已经进行了更改。 - Volatility

Answer 5

这是另一种解决方案，

>>> c = [filter(lambda x: x in b, sublist) for sublist in a]
>>> filter (lambda a: a != '', c)
['g']

- Adem Öztaş

Answer 6

>>> y = [1,23,3]
>>> z = [3,432]
>>> (3 in y) and (3 in z)
True

- MoveFast

---

这需要对每个要检查的元素进行硬编码，而他的问题是要找到一种追踪所有交叉点而不仅仅是一个的方法。 - undefined