我如何有效地找到一个列表的哪些元素在另一个列表中？
How do I efficiently find which elements of a list are in another list?
我想知道 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() 这样的一些函数使用向量运算。我正在寻找类似的东西。
如何让我的代码更有效率？
您可以使用map函数。
在map里面我使用了lambda函数。如果您不熟悉 lambda 函数，那么您可以检查一下。
list_1 = [0,0,1,2,0,0]
list_2 = [1,2,3,4,5,6]
booleans = list(map(lambda e:e in list_2,iter(list_1)))
print(booleans)
输出
[False, False, True, True, False, False]
但是，如果您想要唯一不同的元素，那么您可以使用具有相同代码的 filter 函数来代替 map 函数。
list_1 = [0,0,1,2,0,0]
list_2 = [1,2,3,4,5,6]
new_lst = list(filter(lambda e:e in list_2,iter(list_1)))# edited instead of map use filter.
print(new_lst)
输出
[1, 2]
已编辑
我正在从代码中删除 in 语句，因为 in 也充当循环。我正在使用 timeit 模块进行检查。
您可以将此代码用于包含 True 和 False 的列表。
这种方式比上面一种方式最快
list_1 = [0,0,1,2,0,0]
list_2 = [1,2,3,4,5,6]
set_2 = set(list_2)
booleans = list(map(lambda e:set_2!=set_2-{e},iter(list_1)))
print(booleans)
输出
[False, False, True, True, False, False]
这个用于包含元素的列表。
list_1 = [0,0,1,2,0,0]
list_2 = [1,2,3,4,5,6]
set_2 = set(list_2)
booleans = list(filter(lambda e:set_2!=set_2-{e},iter(list_1))) # edited instead of map use filter
print(booleans)
输出
[1,2]
作为 Op 从不使用 lambda 函数，这是给他的
list_1 = [0,0,1,2,0,0]*100000
list_2 = [1,2,3,4,5,6]*100000
set_2 = set(list_2)
def func():
return set_2!=set_2-{e}
booleans = list(map(func,iter(list_1)))
我知道我的方法不是回答这个问题的最佳方法，因为我从不经常使用 NumPy。
您可以利用 set() 函数的运算符复杂度 O(1) 来提高 for 循环的效率，因此您的最终算法将 运行 in 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)
它作为列表理解甚至更快：
s = set(list_2)
booleans = [i in s for i in list_1]
如果你只想知道元素，你可以使用像这样的集合的交集，这将是一个有效的解决方案，因为使用 set() 函数，已经被其他人优化 Python 工程师：
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))))
使用set()获取每个列表中的唯一项列表
list_1 = [0,0,1,2,0,0]
list_2 = [1,2,3,4,5,6]
booleans = []
set_1 = set(list_1)
set_2 = set(list_2)
if(set_1 & set_2):
print(set_1 & set_2)
else:
print("No common elements")
输出：
{1, 2}
如果你想使用矢量方法，你也可以使用 Numpy isin。它不是最快的方法，如 所示，但它绝对是一个值得考虑的替代方法。
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])
我认为在更大的样本输入上对此处介绍的一些解决方案进行实际计时会很有用。对于此输入和我的机器，我发现 Cardstdani 的方法是最快的，其次是 numpy isin() 方法。
设置 1
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)]
设置 2
list_1 = [random.randint(1, 10_000) for i in range(100_000)]
list_2 = [random.randint(10_001, 20_000) for i in range(100_000)]
计时 - 从最快到最慢排序（设置 1）。
Cardstdani - 方法 1
我建议将 Cardstdani 的方法转换为 列表推导（请参阅 为什么列表推导更快）
s = set(list_2)
booleans = [i in s for i in list_1]
# setup 1
6.01 ms ± 15.7 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
# setup 2
4.19 ms ± 27.7 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
没有列表理解
s = set(list_2)
booleans = []
for i in list_1:
booleans.append(i in s)
# setup 1
7.28 ms ± 27.3 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
# setup 2
5.87 ms ± 8.19 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
Cardstdani - 方法 2（在 Timus 的协助下）
common = set(list_1) & set(list_2)
booleans = [item in common for item in list_1]
# setup 1
8.3 ms ± 34.8 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
# setup 2
6.01 ms ± 26.3 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
使用设置 intersection 方法
common = set(list_1).intersection(list_2)
booleans = [item in common for item in list_1]
# setup 1
10.1 ms ± 29.6 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
# setup 2
4.82 ms ± 19.5 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
numpy 方法 (crissal)
a1 = np.array(list_1)
a2 = np.array(list_2)
a = np.isin(a1, a2)
# setup 1
18.6 ms ± 74.2 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
# setup 2
18.2 ms ± 47.2 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
# setup 2 (assuming list_1, list_2 already numpy arrays)
10.3 ms ± 73.5 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
列表理解
l = [i in list_2 for i in list_1]
# setup 1
4.85 s ± 14.6 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
# setup 2
48.6 s ± 823 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
沙里姆 - 方法 1
booleans = list(map(lambda e: e in list_2, list_1))
# setup 1
4.88 s ± 24.1 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
# setup 2
48 s ± 389 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
使用__contains__方法
booleans = list(map(list_2.__contains__, list_1))
# setup 1
4.87 s ± 5.96 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
# setup 2
48.2 s ± 486 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
Sharim - 方法 2
set_2 = set(list_2)
booleans = list(map(lambda e: set_2 != set_2 - {e}, list_1))
# setup 1
5.46 s ± 56.1 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
# setup 2
11.1 s ± 75.3 ms per loop (mean ± std. dev. of 7 runs, 10 loops 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 for k in range(18)] 中变化 n：
采用以下设置
import random
list_1 = [random.randint(1, n ** 2) for i in range(n)]
list_2 = [random.randint(1, n ** 2) for i in range(n)]
并在 [2 ** k for k in range(18)] 中改变 n，我们得到类似的结果：
采用以下设置
list_1 = list(range(n))
list_2 = list(range(n, 2 * n))
并在 [2 ** k for k in range(18)] 中变化 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)]
并在 [2 ** k for k in range(18)] 中变化 n：
使用 built-in 设置交集方法可能更简单，但如果您有很多要比较的列表，对列表进行排序可能会更快。对列表进行排序是 n ln n，但是一旦对它们进行排序，就可以通过检查元素是否匹配来在线性时间内比较它们，如果不匹配，则前进到列表中当前元素较小的下一个项目。
如果您知道值是 non-negative 并且最大值比列表的长度小得多，那么使用 numpy 的 bincount 可能是使用集合的一个很好的替代方法。
np.bincount(list_1).astype(bool)[list_2]
如果 list_1 和 list_2 恰好是 numpy 数组，这甚至可以比 set + list-comprehension 解决方案快很多。 （在我的测试中，263 微秒对 7.37 毫秒；但如果它们是 python 列表，它比设置的解决方案稍慢，为 8.07 毫秒）
Spybug96 的方法效果最好最快。如果你想得到一个缩进对象与两个集合的共同元素，你可以在最终集合上使用 tuple() 函数：
a = set(range(1, 6))
b = set(range(3, 9))
c = a & b
print(tuple(c))
我想知道 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() 这样的一些函数使用向量运算。我正在寻找类似的东西。
如何让我的代码更有效率？
您可以使用map函数。
在map里面我使用了lambda函数。如果您不熟悉 lambda 函数，那么您可以检查一下。
list_1 = [0,0,1,2,0,0]
list_2 = [1,2,3,4,5,6]
booleans = list(map(lambda e:e in list_2,iter(list_1)))
print(booleans)
输出
[False, False, True, True, False, False]
但是，如果您想要唯一不同的元素，那么您可以使用具有相同代码的 filter 函数来代替 map 函数。
list_1 = [0,0,1,2,0,0]
list_2 = [1,2,3,4,5,6]
new_lst = list(filter(lambda e:e in list_2,iter(list_1)))# edited instead of map use filter.
print(new_lst)
输出
[1, 2]
已编辑
我正在从代码中删除 in 语句，因为 in 也充当循环。我正在使用 timeit 模块进行检查。
您可以将此代码用于包含 True 和 False 的列表。
这种方式比上面一种方式最快
list_1 = [0,0,1,2,0,0]
list_2 = [1,2,3,4,5,6]
set_2 = set(list_2)
booleans = list(map(lambda e:set_2!=set_2-{e},iter(list_1)))
print(booleans)
输出
[False, False, True, True, False, False]
这个用于包含元素的列表。
list_1 = [0,0,1,2,0,0]
list_2 = [1,2,3,4,5,6]
set_2 = set(list_2)
booleans = list(filter(lambda e:set_2!=set_2-{e},iter(list_1))) # edited instead of map use filter
print(booleans)
输出
[1,2]
作为 Op 从不使用 lambda 函数，这是给他的
list_1 = [0,0,1,2,0,0]*100000
list_2 = [1,2,3,4,5,6]*100000
set_2 = set(list_2)
def func():
return set_2!=set_2-{e}
booleans = list(map(func,iter(list_1)))
我知道我的方法不是回答这个问题的最佳方法，因为我从不经常使用 NumPy。
您可以利用 set() 函数的运算符复杂度 O(1) 来提高 for 循环的效率，因此您的最终算法将 运行 in 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)
它作为列表理解甚至更快：
s = set(list_2)
booleans = [i in s for i in list_1]
如果你只想知道元素，你可以使用像这样的集合的交集，这将是一个有效的解决方案，因为使用 set() 函数，已经被其他人优化 Python 工程师：
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))))
使用set()获取每个列表中的唯一项列表
list_1 = [0,0,1,2,0,0]
list_2 = [1,2,3,4,5,6]
booleans = []
set_1 = set(list_1)
set_2 = set(list_2)
if(set_1 & set_2):
print(set_1 & set_2)
else:
print("No common elements")
输出：
{1, 2}
如果你想使用矢量方法，你也可以使用 Numpy isin。它不是最快的方法，如
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])
我认为在更大的样本输入上对此处介绍的一些解决方案进行实际计时会很有用。对于此输入和我的机器，我发现 Cardstdani 的方法是最快的，其次是 numpy isin() 方法。
设置 1
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)]
设置 2
list_1 = [random.randint(1, 10_000) for i in range(100_000)]
list_2 = [random.randint(10_001, 20_000) for i in range(100_000)]
计时 - 从最快到最慢排序（设置 1）。
Cardstdani - 方法 1
我建议将 Cardstdani 的方法转换为 列表推导（请参阅
s = set(list_2)
booleans = [i in s for i in list_1]
# setup 1
6.01 ms ± 15.7 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
# setup 2
4.19 ms ± 27.7 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
没有列表理解
s = set(list_2)
booleans = []
for i in list_1:
booleans.append(i in s)
# setup 1
7.28 ms ± 27.3 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
# setup 2
5.87 ms ± 8.19 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
Cardstdani - 方法 2（在 Timus 的协助下）
common = set(list_1) & set(list_2)
booleans = [item in common for item in list_1]
# setup 1
8.3 ms ± 34.8 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
# setup 2
6.01 ms ± 26.3 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
使用设置 intersection 方法
common = set(list_1).intersection(list_2)
booleans = [item in common for item in list_1]
# setup 1
10.1 ms ± 29.6 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
# setup 2
4.82 ms ± 19.5 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
numpy 方法 (crissal)
a1 = np.array(list_1)
a2 = np.array(list_2)
a = np.isin(a1, a2)
# setup 1
18.6 ms ± 74.2 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
# setup 2
18.2 ms ± 47.2 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
# setup 2 (assuming list_1, list_2 already numpy arrays)
10.3 ms ± 73.5 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
列表理解
l = [i in list_2 for i in list_1]
# setup 1
4.85 s ± 14.6 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
# setup 2
48.6 s ± 823 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
沙里姆 - 方法 1
booleans = list(map(lambda e: e in list_2, list_1))
# setup 1
4.88 s ± 24.1 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
# setup 2
48 s ± 389 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
使用__contains__方法
booleans = list(map(list_2.__contains__, list_1))
# setup 1
4.87 s ± 5.96 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
# setup 2
48.2 s ± 486 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
Sharim - 方法 2
set_2 = set(list_2)
booleans = list(map(lambda e: set_2 != set_2 - {e}, list_1))
# setup 1
5.46 s ± 56.1 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
# setup 2
11.1 s ± 75.3 ms per loop (mean ± std. dev. of 7 runs, 10 loops 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 for k in range(18)] 中变化 n：
采用以下设置
import random
list_1 = [random.randint(1, n ** 2) for i in range(n)]
list_2 = [random.randint(1, n ** 2) for i in range(n)]
并在 [2 ** k for k in range(18)] 中改变 n，我们得到类似的结果：
采用以下设置
list_1 = list(range(n))
list_2 = list(range(n, 2 * n))
并在 [2 ** k for k in range(18)] 中变化 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)]
并在 [2 ** k for k in range(18)] 中变化 n：
使用 built-in 设置交集方法可能更简单，但如果您有很多要比较的列表，对列表进行排序可能会更快。对列表进行排序是 n ln n，但是一旦对它们进行排序，就可以通过检查元素是否匹配来在线性时间内比较它们，如果不匹配，则前进到列表中当前元素较小的下一个项目。
如果您知道值是 non-negative 并且最大值比列表的长度小得多，那么使用 numpy 的 bincount 可能是使用集合的一个很好的替代方法。
np.bincount(list_1).astype(bool)[list_2]
如果 list_1 和 list_2 恰好是 numpy 数组，这甚至可以比 set + list-comprehension 解决方案快很多。 （在我的测试中，263 微秒对 7.37 毫秒；但如果它们是 python 列表，它比设置的解决方案稍慢，为 8.07 毫秒）
Spybug96 的方法效果最好最快。如果你想得到一个缩进对象与两个集合的共同元素，你可以在最终集合上使用 tuple() 函数：
a = set(range(1, 6))
b = set(range(3, 9))
c = a & b
print(tuple(c))