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

问题描述 投票:2回答:3

我有两个清单

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']
]

我想快速确定来自​​list1list2的两个群体,它们在[list1 element, list2 element]拥有所有可能的对ref_list。 在这种情况下,解决方案将是

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

我可以想到一些方法来做这些小清单,但如果list1list2ref_list各有数千个元素需要帮助。

python set compare element
3个回答
0
投票

包含似乎非常快。

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

0
投票

你可以在ref_list中添加每对中的元素来设置set1set2,然后使用list1 = list(set1)list2 = list(set2)。集合不包含重复项,对于数千个元素,这应该很快,因为e in s1集合需要O(1) time on average


0
投票

您可以使用collections.Counterref_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']]
© www.soinside.com 2019 - 2024. All rights reserved.