如何在Python中高效分离N个嵌套字典的公共与唯一结构？

问题描述 #

我拥有N个深度各不相同的嵌套字典，示例如下：

d1 = {'A' : {'B' : 1, 'C': {'D' : 2 } } }
d2 = {'A' : {'C' : {'D' : 2 } , 'E' : 3, 'F' : { 'G' : {'H' : 3 } } } }
# ... 更多字典

需要分离所有字典中的公共结构以及每个字典的唯一结构。以d1和d2为例，期望输出为：

common_d = {'A' : { 'C' : {'D' : 2 } } }
unique_d1 = {'A' : {'B' : 1 } }
unique_d2 = {'A' : {'E' : 3, 'F' : { 'G' : {'H' : 3 } } } }

解决方案 #

核心思路 #

通过递归遍历所有字典，先找出所有字典共有的、且对应值完全一致的键值对（包括嵌套字典的层级结构），得到公共结构；再对每个原字典，递归移除公共结构中的内容，剩余部分即为该字典的唯一结构。

实现代码 #

def get_common_dict(dicts):
    if not dicts:
        return {}
    # 从第一个字典开始，逐步与其他字典求交集
    common = dicts[0].copy()
    for d in dicts[1:]:
        common = _intersect_dicts(common, d)
        if not common:
            break
    return common

def _intersect_dicts(d1, d2):
    intersect = {}
    for k, v1 in d1.items():
        if k in d2:
            v2 = d2[k]
            if isinstance(v1, dict) and isinstance(v2, dict):
                # 嵌套字典递归求交集
                nested_intersect = _intersect_dicts(v1, v2)
                if nested_intersect:
                    intersect[k] = nested_intersect
            elif v1 == v2:
                # 值相等则保留
                intersect[k] = v1
    return intersect

def get_unique_dict(original, common):
    unique = {}
    for k, v in original.items():
        if k not in common:
            # 原字典独有的键，直接保留
            unique[k] = v.copy() if isinstance(v, dict) else v
        else:
            v_common = common[k]
            if isinstance(v, dict) and isinstance(v_common, dict):
                # 嵌套字典递归求唯一部分
                nested_unique = get_unique_dict(v, v_common)
                if nested_unique:
                    unique[k] = nested_unique
            # 若值与公共结构一致，则不保留
    return unique

使用示例 #

# 定义示例字典
d1 = {'A' : {'B' : 1, 'C': {'D' : 2 } } }
d2 = {'A' : {'C' : {'D' : 2 } , 'E' : 3, 'F' : { 'G' : {'H' : 3 } } } }
dicts = [d1, d2]

# 计算公共结构
common_d = get_common_dict(dicts)
# 计算每个字典的唯一结构
unique_d1 = get_unique_dict(d1, common_d)
unique_d2 = get_unique_dict(d2, common_d)

# 输出结果
print("common_d =", common_d)
print("unique_d1 =", unique_d1)
print("unique_d2 =", unique_d2)

运行后输出：

common_d = {'A': {'C': {'D': 2}}}
unique_d1 = {'A': {'B': 1}}
unique_d2 = {'A': {'E': 3, 'F': {'G': {'H': 3}}}}

效率说明 #

该实现采用递归遍历，时间复杂度与所有字典的总键数成正比，每个键最多被遍历N次（N为字典数量），在大多数业务场景下足够高效。若需处理超大规模嵌套字典，可考虑将递归改为迭代式遍历，或加入缓存机制进一步优化。

内容的提问来源于stack exchange，提问作者Kspr