Снижение сложности: найти общие элементы в списках

Question

Простая настройка: у меня есть список (примерно 40 000 записей), содержащий списки строк (каждая с 2-15 элементами). Я хочу сравнить все подсписки, чтобы проверить, имеют ли они общий элемент (они разделяют не более одного). В конце я хочу создать словарь (график, если хотите), в котором индекс каждого подсписка используется в качестве ключа, а его значения - это индексы других подсписков, с которыми он имеет общие элементы.

Например

lst = [['dam', 'aam','adm', 'ada', 'adam'], ['va','ea','ev','eva'], ['va','aa','av','ava']]

должно дать следующее:

dic = {0: [], 1: [2], 2: [1]}

Моя проблема в том, что я нашел решение, но оно очень дорого в вычислительном отношении. Сначала я написал функцию для вычисления пересечения двух списков:

def intersection(lst1, lst2): 

    temp = set(lst2) 
    lst3 = [value for value in lst1 if value in temp] 
    return lst3 

Тогда я бы перебрал все списки для проверки на пересечения:

dic = {}
iter_range = range(len(lst))

#loop over all lists where k != i
for i in iter_range:

    #create range that doesn't contain i
    new_range = list(iter_range)
    new_range.remove(i)

    lst = []

    for k in new_range:
        #check if the lists at position i and k intersect
        if len(intersection(mod_names[i], mod_names[k])) > 0:
            lst.append(k)

    # fill dictionary 
    dic[i] = lst

Я знаю, что циклы for работают медленно, и что я перебираю список излишне часто (в приведенном выше примере я сравниваю 1 с 2, затем 2 с 1), но я не знаю, как это изменить чтобы программа работала быстрее.

Answer 1

Вы можете создать dict word_occurs_in, который будет хранить данные о том, какое слово встречается в каких списках, для вашего образца это будет:

{'dam': [0], 'aam': [0], 'adm': [0], 'ada': [0], 'adam': [0], 'va': [1, 2], «ea»: [1], «ev»: [1], «eva»: [1], «aa»: [2], «av»: [2], «ava»: [2]}

Затем вы можете создать новый диктант, назовем его result, в котором вы должны сохранить конечный результат, например, {0: [], 1: [2], 2: [1]} в вашем случае.

Теперь, чтобы получить result из word_occurs_in, вы должны просмотреть значения word_occurs_in и посмотреть, есть ли в списке более одного элемента. Если это так, то вам просто нужно добавить все остальные значения, кроме значения наблюдаемого в данный момент ключа в result. Например, при проверке значения [1, 2] (для ключа 'va') вы 'добавите 1 к значению, соответствующему 2 в result dict, и добавите 2 к значению, соответствующему ключ 1. Надеюсь, это поможет.

В моем понимании, самая большая сложность вашего кода заключается в повторении списка из 40 тыс. Записей дважды, поэтому этот подход повторяет список только один раз, но использует немного больше места.

Возможно, я не объяснил себя достаточно, поэтому вот код:

from collections import defaultdict

lst = [['dam', 'aam', 'adm', 'ada', 'adam'], ['va', 'ea', 'ev', 'eva'], ['va', 'aa', 'av', 'ava']]

word_occurs_in = defaultdict(list)

for idx, l in enumerate(lst):
    for i in l:
        word_occurs_in[i].append(idx)

print(word_occurs_in)

result = defaultdict(list)
for v in word_occurs_in.values():
    if len(v) > 1:
        for j in v:
            result[j].extend([k for k in v if k != j])

print(result)