Нахождение пар элементов из двух наборов, которые имеют предопределенное отношение - PullRequest
Новая
       24

Нахождение пар элементов из двух наборов, которые имеют предопределенное отношение

2 голосов
/ 29 апреля 2019

У меня есть два списка 

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, которые имеют все возможные пары [list1 element, list2 element] в ref_list.
В этом случае решение будет 

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

Я могу придумать несколько способов сделать это для такихнебольшие списки, но нужна помощь, если list1, list2 и ref_list имеют тысячи элементов в каждом.

Ответы [ 3 ]

0 голосов
/ 30 апреля 2019

Вы можете добавить элементы из каждой пары в ref_list для наборов set1 и set2, затем использовать list1 = list(set1) и list2 = list(set2).Наборы не содержат дубликатов, и это должно быть быстрым для тысяч элементов, поскольку e in s1 для наборов занимает в среднем O (1) времени .

0 голосов
/ 30 апреля 2019

Вы можете использовать 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']]
0 голосов
/ 30 апреля 2019

Установка включения кажется довольно быстрой. 

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