Python如何高效处理马尔可夫伪词生成用的复杂嵌套字典？

核心思路 #

针对需求可以通过单趟自底向上递归+结构指纹记忆化的方案解决性能问题，核心逻辑如下：

• 为每个唯一的子字典生成可哈希的结构指纹：将当前节点排序后的键与对应子节点的指纹组合为元组，相同结构的子字典会生成完全一致的指纹，解决字典不可哈希无法做缓存的问题。
• 递归过程中一次性完成三项处理：处理完所有子节点后，按顺序执行「修剪空分支」→「合并单父子分支」→「键排序」，不需要多趟遍历整棵树。
• 全局维护记忆化缓存，指纹相同的子结构直接复用已处理的结果，避免重复计算。

代码实现 #

from typing import Dict, Tuple, Union

# 记忆化缓存：key为结构指纹id，value为对应处理结果的元信息
cache = {}
# 指纹生成计数器，为唯一结构分配极简的唯一id，避免长元组指纹占用过多内存
fingerprint_counter = 0
# 结构到指纹的映射：key是(排序后的键元组, 子指纹元组)，value是分配的指纹id
struct_to_fingerprint = {}

def process_markov_dict(node: Dict[Tuple[str, int], Dict]) -> Union[Dict, Tuple]:
    """
    输入原始嵌套马尔可夫字典，返回处理后的结构
    返回值如果是元组，说明是合并了单分支的链；如果是字典，说明是多分支节点
    """
    global fingerprint_counter
    
    # 第一步：递归处理所有子节点，同时收集子节点的指纹
    processed_children = []
    child_fingerprints = []
    for key, child in node.items():
        # 子节点是空字典直接跳过，顺便完成剪空分支的第一步筛选
        if not child:
            continue
        processed_child = process_markov_dict(child)
        processed_children.append((key, processed_child))
        # 生成子节点的指纹（合并后的元组直接作为指纹元素，字典取缓存的结构指纹）
        if isinstance(processed_child, tuple):
            child_fp = processed_child
        else:
            child_fp = cache[id(processed_child)]["fp"]
        child_fingerprints.append((key, child_fp))
    
    # 第二步：剪空分支，如果处理后没有有效子节点直接返回空
    if not processed_children:
        return {}
    
    # 第三步：生成当前结构的指纹，查询记忆化缓存
    child_fingerprints_sorted = tuple(sorted(child_fingerprints))
    if child_fingerprints_sorted in struct_to_fingerprint:
        # 已有相同结构直接复用缓存结果
        fp = struct_to_fingerprint[child_fingerprints_sorted]
        return cache[fp]["result"]
    
    # 第四步：合并仅含单个子分支的父子节点
    if len(processed_children) == 1:
        key, child = processed_children[0]
        # 子节点是已合并的元组就直接拼接，否则组合为新元组
        merged = (key,) + child if isinstance(child, tuple) else (key, child)
        # 存入缓存
        fp = fingerprint_counter
        fingerprint_counter += 1
        struct_to_fingerprint[child_fingerprints_sorted] = fp
        cache[fp] = {"fp": child_fingerprints_sorted, "result": merged}
        return merged
    
    # 第五步：多分支节点按键排序生成新字典
    processed_children_sorted = sorted(processed_children, key=lambda x: x[0])
    sorted_dict = dict(processed_children_sorted)
    # 存入缓存
    fp = fingerprint_counter
    fingerprint_counter += 1
    struct_to_fingerprint[child_fingerprints_sorted] = fp
    cache[fp] = {"fp": child_fingerprints_sorted, "result": sorted_dict}
    return sorted_dict

优化效果说明 #

• 遍历次数从3次降为1次，无额外冗余遍历开销。
• 重复子结构仅处理一次，针对存在大量重复子结构的马尔可夫链场景，实际运行效率可以提升数倍到数十倍不等。
• 递归深度最多为15层，完全不会触发栈溢出问题，也不需要额外修改Python默认递归深度配置。

内容的提问来源于stack exchange，提问作者Ξένη Γήινος