如何有效地找到列表中的哪些元素在另一个列表中？

Question

我想知道list_1的哪些元素在list_2中。我需要输出一个有序的布尔值列表。但是我想避免for循环，因为两个列表都有超过200万个元素。

这就是我所拥有的，它是有效的，但它太慢了：

list_1 = [0,0,1,2,0,0]
list_2 = [1,2,3,4,5,6]

booleans = []
for i in list_1:
   booleans.append(i in list_2)

# booleans = [False, False, True, True, False, False]

我可以拆分列表并使用多线程，但如果可能的话，我更喜欢一个更简单的解决方案。我知道一些函数，比如sum（）使用向量运算。我在找类似的东西。

如何让我的代码更高效？

Answer 1

如果你想使用向量方法，你也可以使用Numpy isin。这不是最快的方法，正如oda的优秀帖子所展示的，但它绝对是一种可以考虑的替代方法。

import numpy as np

list_1 = [0,0,1,2,0,0]
list_2 = [1,2,3,4,5,6]

a1 = np.array(list_1)
a2 = np.array(list_2)

np.isin(a1, a2)
# array([False, False,  True,  True, False, False])

Answer 2

我认为在更大的样本输入上实际计算一些解决方案的时间会很有用。对于这个输入和我的机器，我发现Cardstdani的方法是最快的，其次是Numpyisin（）方法。

设置

import random

list_1 = [random.randint(1, 10_000) for i in range(100_000)]
list_2 = [random.randint(1, 10_000) for i in range(100_000)]

计时-从最快到最慢排序。

Cardstdani-方法1

列表理解（关于为什么列表理解更快，请参阅此问题）

s = set(list_2)
booleans = [i in s for i in list_1]

6.47 ms ± 54.9 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

没有列表理解

s = set(list_2)
booleans = []
for i in list_1:
   booleans.append(i in s)

8.04 ms ± 35.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Cardstdani-方法2（在Timus的协助下）

common = set(list_1) & set(list_2)
booleans = [item in common for item in list_1]

8.55 ms ± 47.8 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

臀入路（嵴）

a1 = np.array(list_1)
a2 = np.array(list_2)

np.isin(a1, a2)

19.3 ms ± 54.6 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

列表理解

l = [i in list_2 for i in list_1]

5.04 s ± 31.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

伊斯兰教法——方法1

booleans = list(map(lambda e:e in list_2, iter(list_1)))

5.17 s ± 26.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

伊斯兰教法——方法2

set_2 = set(list_2)
booleans = list(map(lambda e: set_2 != set_2 - {e}, list_1))

5.98 s ± 22.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

伊斯兰教法——方法3

set_2 = set(list_2)
booleans = list(map(lambda e: set_2 != set_2 - {e}, iter(list_1)))

6.05 s ± 44.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

改变输入的长度

对上面应用稍微不同的设置

import random 

list_1 = [random.randint(1, n) for i in range(n)]
list_2 = [random.randint(1, n) for i in range(n)]

并在[2**k代表范围（20）内的k]中改变n（显示了每个人的最佳方法）：

采用以下设置

import random 

list_1 = [random.randint(1, n) for i in range(10 * n)]
list_2 = [random.randint(1, n) for i in range(10 * n)]

通过改变n中的[2**k表示范围（19）]中的k，我们得到了类似的结果：

Answer 3

您可以利用O（1）in运算符复杂度的set（）函数来提高for循环的效率，这样最终的算法将在O（n）时间内运行，而不是O（n*n）：

list_1 = [0,0,1,2,0,0]
list_2 = [1,2,3,4,5,6]

s = set(list_2)
booleans = []
for i in list_1:
   booleans.append(i in s)
print(booleans)

如果您只想知道元素，可以使用这样的集合交集，这将是一个有效的解决方案，因为使用了其他Python工程师已经优化过的set（）函数：

list_1 = [0,0,1,2,0,0]
list_2 = [1,2,3,4,5,6]

print(set(list_1).intersection(set(list_2)))

输出：

{1, 2}

此外，要提供列表格式输出，可以使用list（）函数将结果集转换为列表：

print(list(set(list_1).intersection(set(list_2))))