Подтверждение 2 больших Python словарей

Question

Скажем, у меня есть 2 словаря, каждый из которых содержит около 100000 записей (каждый может быть разной длины):

dict1 = {"a": ["w", "x"], "b":["y"], "c":["z"] ...}
dict2 = {"x": ["a", "b"], "y":["b", "d"], "z":["d"] ...}

Мне нужно выполнить операцию с использованием этих двух словарей:

• Рассматривать каждый элемент dict как набор сопоставлений (т. Е. Список всех сопоставлений в dict1 будет "a"->"w", "a"->"x", "b"->"y" и "c"->"z")
• Хранить сопоставления только в dict1 если обратное отображение существует в dict2.

В результате получается следующий словарь: {"a": ["x"], "b", ["y"]}

Мое текущее решение использует 2 m*n все нули данных, где m и n - это длины dict1 и dict2 соответственно, метки индекса - это ключи dict1, а метки столбца - ключи dict2.

Для первого кадра данных я вставляю 1 в каждое значение, где метка индекса -> метка столбца представляет отображение в dict1. Для второго фрейма данных я вставляю 1 в каждое значение, где метка столбца -> метка индекса представляет отображение в dict2.

Затем я выполняю произведение размера элемента между двумя фреймами данных, которое оставляет только значения с отображением "a1"->"x1" в dict1 и "x1"->"a1" в dict2.

Однако это занимает слишком много памяти и очень дорого. Есть ли альтернативный алгоритм, который я могу использовать?

Answer 1

Как насчет использовать ту же идею, но заменить разреженную матрицу, которую вы используете, набором пар ключей? Что-то вроде:

import collections
def fn(dict1, dict2):
    mapping_set = set()
    for k, vv in dict2.items():
        for v in vv:
            mapping_set.add((k, v))
    result_dict = collections.defaultdict(list)
    for k, vv in dict1.items():
        for v in vv:
            if (v, k) in mapping_set:  # Note reverse order of k and v
                result_dict[k].append(v)
    return result_dict

Обновление : будет использоваться O(total number of values in dict2) памяти и O(total number of values in dict1) + O(total number of values in dict2) времени - оба линейные. Невозможно решить проблему алгоритмически быстрее, так как каждое значение в каждом dict нужно посетить хотя бы один раз.

Answer 2

Учитывая, что у вас есть python объекты для начала, вы можете остаться в домене python. Если вам все равно потребуется пройти через весь dict, чтобы создать свою матрицу, вы можете обнаружить, что фильтрация на месте не займет много времени.

default = ()
result = {k: v for k, v in dict1.items() if k in dict2.get(v, default)}

Если ваш список короткий, это будет вполне нормально , Если они содержат много элементов, линейный поиск начнет сравниваться с издержками поиска по набору. В этом случае вы можете захотеть предварительно обработать dict2, чтобы содержать set s, а не списки:

dict2 = {k: set(v) for k, v in dict2.items}

или на месте

for k, v in dict2.items():
    dict2[k] = set(v)