python - 确认 2 个大型 Python 词典

Question

假设我有 2 个字典，每个字典大约有 100000 个条目(每个可以有不同的长度):

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

我需要使用这两个字典执行操作:

将每个字典项视为一组映射(即 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

如何使用相同的想法，但用一组 key 对替换您正在使用的稀疏矩阵？就像是:

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)时间 - 两者都是线性的。由于每个字典中的每个值都必须至少访问一次，因此不可能在算法上更快地解决问题。