Найти элементы, которые появляются вместе в нескольких списках - PullRequest
Новая
       28

Найти элементы, которые появляются вместе в нескольких списках

0 голосов
/ 30 марта 2020

Я пытаюсь написать эффективный код python, который будет идентифицировать элементы, которые появляются вместе в нескольких списках. Например, в словаре списков 

list_of_lists = {'lista':list('abcdefhmqr'),
                 'listb':list('abdgklmr'),
                 'listc':list('abcdgjkmr'),
                 'listd':list('abcdglmrt'),
                 'liste':list('admoprst')}

«adrm» появляются вместе во всех пяти списках, тогда как «abdm», «abdr», «abmr» и «bdmr» появляются вместе в четырех списках, и многие комбинации из четырех букв появляются в трех или двух списках.

Вот код: 

def make_dict(lists):
    # creates a dictionary with each unique item as the key,
    # and a set of lists the item appears on as the value
    letter_dict={}
    for item in lists.items():
        for letter in item[1]:
            if letter in letter_dict:
                letter_dict[letter].add(item[0])
            else:
                letter_dict[letter] = set([item[0]])
    return OrderedDict(sorted(letter_dict.items(),key=lambda x:x[0]))

def find_matches(dictionary):
    # takes a dictionary with tuples of list elements as keys
    # and lists they appear on as values, and finds the intersection with 
    # the master list of elements and their lists
    matches={}
    for key in dictionary.keys():
        index_of_key = index_of_attr_keys.index(key[-1])
        for next_key in islice(master_list,index_of_key+1,None):
            intersection = dictionary[key] & master_list[next_key]
            if len(intersection)>1:
                new_key = set(key)
                new_key.add(next_key[0])
                new_key = tuple(sorted(new_key))
                matches[new_key] = intersection
    return matches

master_list = make_dict(list_of_lists)
index_of_attr_keys = sorted(master_list.keys())

Я могу итеративно создавать словари с ключами кортежей с двумя, тремя, четырьмя и т. д. c. items 

doubles = find_matches(master_list)
triples = find_matches(doubles)
quads = find_matches(triples)

Мой код работает на этом игрушечном примере, но он не особенно быстр, когда я запускаю его на своем фактическом наборе данных, который содержит более 84 000 уникальных элементов, появляющихся в сотнях списков. Начиная с моего списка из более чем 84 000 уникальных элементов, для создания списка из 1,2 миллиона пар, которые появляются вместе в более чем одном списке, требуется час, и от этого все становится длиннее. Мне интересно, есть ли более быстрый способ сделать это.

1 Ответ

1 голос
/ 30 марта 2020

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

set.intersection(*[set(x) for x in list_of_lists.values()])

Вывод: 

 {'a', 'd', 'm', 'r'}
...