python - 如何在两个字典中找到匹配值的字典键？

Question

我有两个字典将 ID 映射到值。为简单起见，假设这些是字典:

d_source = {'a': 1, 'b': 2, 'c': 3, '3': 3}
d_target = {'A': 1, 'B': 2, 'C': 3, '1': 1}

顾名思义，字典不是对称的。 我想从值匹配的字典 d_source 和 d_target 中获取 keys 的字典。生成的字典会将 d_source 键作为其自己的键，并将 d_target 键作为该键值(在 list、tuple 中) 或 set 格式)。

这将是上述示例的预期返回值应为以下列表:

{'a': ('1', 'A'),
 'b': ('B',),
 'c': ('C',),
 '3': ('C',)}

有两个有点similar questions ，但这些解决方案无法轻松应用于我的问题。

数据的一些特征:

1. 源通常小于目标。拥有大约几千个来源(顶部)和更多的目标。
2. 同一字典中的重复项(d_source 和 d_target)不太可能出现值。
3. 预期找到的匹配项(粗略估计)不超过 d_source 项的 50%。
4. 所有键都是整数。

这个问题的最佳(性能方面)解决方案是什么？ 将数据建模为其他数据类型以提高性能是完全可以的，即使在使用第三方库时也是如此(我在想 numpy)

Answer 1

所有的答案都有 O(n^2) 的效率，这不是很好所以我想自己回答。

我使用 2(source_len) + 2(dict_count)(dict_len) 内存并且我有 O(2n) 效率，我相信这是你能得到的最好的.

给你:

from collections import defaultdict

d_source = {'a': 1, 'b': 2, 'c': 3, '3': 3}
d_target = {'A': 1, 'B': 2, 'C': 3, '1': 1}

def merge_dicts(source_dict, *rest):
    flipped_rest = defaultdict(list)
    for d in rest:
        while d:
            k, v = d.popitem()
            flipped_rest[v].append(k)
    return {k: tuple(flipped_rest.get(v, ())) for k, v in source_dict.items()}

new_dict = merge_dicts(d_source, d_target)

顺便说一句，我使用元组是为了不将结果列表链接在一起。

---

当您为数据添加规范时，这里有一个更匹配的解决方案:

d_source = {'a': 1, 'b': 2, 'c': 3, '3': 3}
d_target = {'A': 1, 'B': 2, 'C': 3, '1': 1}

def second_merge_dicts(source_dict, *rest):
    """Optimized for ~50% source match due to if statement addition.

    Also uses less memory.
    """
    unique_values = set(source_dict.values())
    flipped_rest = defaultdict(list)
    for d in rest:
        while d:
            k, v = d.popitem()
            if v in unique_values:
                flipped_rest[v].append(k)
    return {k: tuple(flipped_rest.get(v, ())) for k, v in source_dict.items()}

new_dict = second_merge_dicts(d_source, d_target)