从具有预定义关系的两个集合中查找元素对

Question

我有两个列表

list1 = ['a', 'b', 'c', 'd']
list2 = ['e', 'f', 'g', 'h']

我以前知道，其中一些元素是通过另一个列表相关的

ref_list = [
   ['d', 'f'], ['a', 'e'], ['b', 'g'], ['c', 'f'], ['a', 'g'],
   ['a', 'f'], ['b', 'e'], ['b', 'f'], ['c', 'e'], ['c', 'g']
]

我想快速识别list1和list2的两组，这些组在ref_list中具有所有可能的[list1 element, list2 element]。
在这种情况下，解决方案将是

[['a', 'b', 'c'], ['e', 'f', 'g']]

我可以想到一些方法可以在如此小的列表中执行此操作，但是如果list1，list2和ref_list每个都有成千上万个元素。

Answer 1

集合似乎很快。

import random
import string
list1 = [random.choice(string.ascii_letters) + random.choice(string.ascii_letters) + random.choice(string.ascii_letters) for _ in xrange(9999)]
# len(list1) == 9999    
list2 = [random.choice(string.ascii_letters) + random.choice(string.ascii_letters) + random.choice(string.ascii_letters) for _ in xrange(9999)]
# len(list2) == 9999
ref_list = [[random.choice(string.ascii_letters) + random.choice(string.ascii_letters) + random.choice(string.ascii_letters), random.choice(string.ascii_letters) + random.choice(string.ascii_letters) + random.choice(string.ascii_letters)] for _ in xrange(9999)]
# len(ref_list) == 9999
refs1 = set([t[0] for t in ref_list])
# CPU times: user 2.45 ms, sys: 348 µs, total: 2.8 ms
# Wall time: 2.2 ms
# len(refs1) == 9656 for this run
refs2 = set([t[1] for t in ref_list])
# CPU times: user 658 µs, sys: 3.92 ms, total: 4.58 ms
# Wall time: 4.02 ms
# len(refs2) == 9676 for this run
list1_filtered = [v for v in list1 if v in refs1]
# CPU times: user 1.19 ms, sys: 4.34 ms, total: 5.53 ms
# Wall time: 3.76 ms
# len(list1_filtered) == 702 for this run
list2_filtered = [v for v in list2 if v in refs2]
# CPU times: user 3.05 ms, sys: 4.29 ms, total: 7.33 ms
# Wall time: 4.51 ms
# len(list2_filtered) == 697 for this run

Answer 2

您可以将ref_list中每个对的元素添加到设置set1和set2，然后使用list1 = list(set1)和list2 = list(set2)。集合不包含重复项，这应该是数千个元素的快速，因为集合的e in s1平均需要O(1(时间。

Answer 3

您可以使用 collections.Counter来生成ref_list中项目的计数，并使用它们过滤两个列表中不超过一次的项目：

from collections import Counter
[[i for i in lst if counts.get(i, 0) > 1] for lst, ref in zip((list1, list2), zip(*ref_list)) for counts in (Counter(ref),)]

此返回：

[['a', 'b', 'c'], ['e', 'f', 'g']]