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

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

我认为在更大的样本输入上实际计算此处提出的一些解决方案会很有用。对于这个输入和在我的机器上，我发现 Cardstdani 的方法是最快的，其次是 方法numpy isin()。

\n

设置1

\n

import random\n\nlist_1 = [random.randint(1, 10_000) for i in range(100_000)]\nlist_2 = [random.randint(1, 10_000) for i in range(100_000)]\n

\n

设置2

\n

list_1 = [random.randint(1, 10_000) for i in range(100_000)]\nlist_2 = [random.randint(10_001, 20_000) for i in range(100_000)]\n

\n

计时- 从最快到最慢排序（设置 1）。

\n

Cardstdani - 方法 1

\n\n

我建议将 Cardstdani 的方法转换为列表理解（请参阅此问题了解为什么列表理解更快）

\n

s = set(list_2)\nbooleans = [i in s for i in list_1]\n\n# setup 1\n6.01 ms \xc2\xb1 15.7 \xc2\xb5s per loop (mean \xc2\xb1 std. dev. of 7 runs, 1,000 loops each)\n# setup 2\n4.19 ms \xc2\xb1 27.7 \xc2\xb5s per loop (mean \xc2\xb1 std. dev. of 7 runs, 1,000 loops each)\n

\n

没有列表理解

\n

s = set(list_2)\nbooleans = []\nfor i in list_1:\n   booleans.append(i in s)\n\n# setup 1\n7.28 ms \xc2\xb1 27.3 \xc2\xb5s per loop (mean \xc2\xb1 std. dev. of 7 runs, 1,000 loops each)\n# setup 2\n5.87 ms \xc2\xb1 8.19 \xc2\xb5s per loop (mean \xc2\xb1 std. dev. of 7 runs, 1,000 loops each)\n

\n

Cardstdani - 进场 2（在 Timus 的协助下）

\n\n

common = set(list_1) & set(list_2)\nbooleans = [item in common for item in list_1]\n\n# setup 1\n8.3 ms \xc2\xb1 34.8 \xc2\xb5s per loop (mean \xc2\xb1 std. dev. of 7 runs, 1,000 loops each)\n# setup 2\n6.01 ms \xc2\xb1 26.3 \xc2\xb5s per loop (mean \xc2\xb1 std. dev. of 7 runs, 1,000 loops each)\n

\n

使用设置intersection方法

\n

common = set(list_1).intersection(list_2)\nbooleans = [item in common for item in list_1]\n\n# setup 1\n10.1 ms \xc2\xb1 29.6 \xc2\xb5s per loop (mean \xc2\xb1 std. dev. of 7 runs, 1,000 loops each)\n# setup 2\n4.82 ms \xc2\xb1 19.5 \xc2\xb5s per loop (mean \xc2\xb1 std. dev. of 7 runs, 1,000 loops each)\n

\n

numpy 方法（关键）

\n\n

a1 = np.array(list_1)\na2 = np.array(list_2)\n\na = np.isin(a1, a2)\n\n# setup 1\n18.6 ms \xc2\xb1 74.2 \xc2\xb5s per loop (mean \xc2\xb1 std. dev. of 7 runs, 1,000 loops each)\n# setup 2\n18.2 ms \xc2\xb1 47.2 \xc2\xb5s per loop (mean \xc2\xb1 std. dev. of 7 runs, 1,000 loops each)\n# setup 2 (assuming list_1, list_2 already numpy arrays)\n10.3 ms \xc2\xb1 73.5 \xc2\xb5s per loop (mean \xc2\xb1 std. dev. of 7 runs, 1,000 loops each)\n

\n

列表理解

\n\n

l = [i in list_2 for i in list_1]\n\n# setup 1\n4.85 s \xc2\xb1 14.6 ms per loop (mean \xc2\xb1 std. dev. of 7 runs, 10 loops each)\n# setup 2\n48.6 s \xc2\xb1 823 ms per loop (mean \xc2\xb1 std. dev. of 7 runs, 10 loops each)\n

\n

沙里姆 - 方法 1

\n\n

booleans = list(map(lambda e: e in list_2, list_1))\n\n# setup 1\n4.88 s \xc2\xb1 24.1 ms per loop (mean \xc2\xb1 std. dev. of 7 runs, 10 loops each)\n# setup 2\n48 s \xc2\xb1 389 ms per loop (mean \xc2\xb1 std. dev. of 7 runs, 10 loops each)\n

\n

使用__contains__方法

\n

booleans = list(map(list_2.__contains__, list_1))\n\n# setup 1\n4.87 s \xc2\xb1 5.96 ms per loop (mean \xc2\xb1 std. dev. of 7 runs, 10 loops each)\n# setup 2\n48.2 s \xc2\xb1 486 ms per loop (mean \xc2\xb1 std. dev. of 7 runs, 10 loops each)\n

\n

沙里姆 - 方法 2

\n\n

set_2 = set(list_2)\nbooleans = list(map(lambda e: set_2 != set_2 - {e}, list_1))\n\n# setup 1\n5.46 s \xc2\xb1 56.1 ms per loop (mean \xc2\xb1 std. dev. of 7 runs, 10 loops each)\n# setup 2\n11.1 s \xc2\xb1 75.3 ms per loop (mean \xc2\xb1 std. dev. of 7 runs, 10 loops each)\n

\n

改变输入的长度

\n\n

采用以下设置

\n

import random \n\nlist_1 = [random.randint(1, n) for i in range(n)]\nlist_2 = [random.randint(1, n) for i in range(n)]\n

\n

并变化n于[2 ** k for k in range(18)]：

\n

\n

采用以下设置

\n

import random \n\nlist_1 = [random.randint(1, n ** 2) for i in range(n)]\nlist_2 = [random.randint(1, n ** 2) for i in range(n)]\n

\n

并改变n，[2 ** k for k in range(18)]我们得到类似的结果：

\n

\n

采用以下设置

\n

list_1 = list(range(n))\nlist_2 = list(range(n, 2 * n))\n

\n

并变化n于[2 ** k for k in range(18)]：

\n

\n

采用以下设置

\n

import random \n\nlist_1 = [random.randint(1, n) for i in range(10 * n)]\nlist_2 = [random.randint(1, n) for i in range(10 * n)]\n

\n

并变化n于[2 ** k for k in range(18)]：

\n

\n

Answer 2

您可以利用函数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)

作为列表理解，它甚至更快：

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))))

Answer 3

如果你想使用向量方法，你也可以使用 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 4

您可以使用该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]

但是，如果您想要唯一不相同的元素，那么map您可以使用filter具有相同代码的函数来代替函数。

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 函数，所以 this.

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太多。