在两个列表中查找重叠对象的最快方法

Question

我有两个自定义对象列表train和test，分别大小为9904和7223。 每个列表中的元素都是唯一的。你知道吗

我想找到两个列表中存在的元素。目前我正在使用以下方法，但速度非常慢：

overlap = [e for e in test if e in train]

有没有更快的方法来实现这一点？

Answer 1

@yatu建议使用sets，因为这使得成员资格测试更快——对于一个列表，解释器必须依次查看每个元素，而对于一个集合（或者一个dict，尽管这无关紧要），则使用散列技术。您可以简单地将列表替换为它们的等价集合（通过对列表应用set()构造函数获得），您应该会看到一些加速。你知道吗

但是，有一些特定的方法来确定两个集合的交集和并集。只要订购不重要*，以下是您可能的做法：

train_set = set(train)  # Use frozenset if no mutation is required
test_set = set(test)
common_elements = train_set & test_set  # or, equivalently
common_elements = train_set.intersection(test_set)

*在Python3.7之前，集合或字典中元素的顺序是不能保证的。你知道吗

Answer 2

为了完成@Jeff的回答，我们可以比较两种方法的计算时间：

import numpy as np
import time

test = np.random.randint(1,50000,10000)
train = np.random.randint(1,50000,10000)

start_list = time.time()
overlap = [e for e in test if e in train]
end_list = time.time()
print("with list comprehension: " + str(end_list - start_list))

set_test = set(test)
set_train = set(train)

start_set = time.time()
overlap = set_test.intersection(set_train)
end_set = time.time()
print("with sets: " + str(end_set - start_set))

我们得到输出：

with list comprehension: 0.08894968032836914
with sets: 0.0003533363342285156

所以使用集合的方法要快300倍。你知道吗

Answer 3

set_test = set(e)

set_train = set(train)

overlap = set_test.intersection(set_train)