Python如何高效将4个通过EntityId关联的字典列表嵌套合并为结构化列表

原有代码的时间复杂度为O(证书数量 * (实体数量 + 日志数量 + 联系人数量))：每处理1条证书记录，都要全量遍历实体、日志、联系人三个列表做匹配，十万级数据量下总运算量可达百亿次，是耗时高的根本原因。

核心思路是预构建关联数据的id映射索引，把匹配操作从O(N)降为O(1)，整体时间复杂度降到线性的O(实体数量 + 日志数量 + 联系人数量 + 证书数量)，百万级数据也可以在秒级完成处理。

优化后代码 #

from dataclasses import asdict
from typing import List
from collections import defaultdict

def cert_and_details(entities: List[Entity], 
                    certificates: List[Certificate], 
                    req_logs: List[DocumentRequestHistory], 
                    recipients: List[Recipient]) -> List[dict]:
    # 1. 预构建三个关联表的entityid映射索引，key为entityid，value为对应记录的字典列表
    entity_map = defaultdict(list)
    for ent in entities:
        ent_dict = asdict(ent)
        entity_map[ent_dict["entityid"]].append(ent_dict)
    
    log_map = defaultdict(list)
    for log in req_logs:
        log_dict = asdict(log)
        log_map[log_dict["entityid"]].append(log_dict)
    
    recipient_map = defaultdict(list)
    for rec in recipients:
        rec_dict = asdict(rec)
        recipient_map[rec_dict["entityid"]].append(rec_dict)

    # 2. 遍历证书列表，直接从索引取关联数据，无需循环遍历
    results = []
    for cert in certificates:
        cert_dict = asdict(cert)
        cert_entity_id = cert_dict["entityid"]
        # 直接从映射取，无匹配则返回空列表，和原逻辑完全一致
        cert_dict["logs"] = log_map.get(cert_entity_id, [])
        cert_dict["linkedentity"] = entity_map.get(cert_entity_id, [])
        cert_dict["recipients"] = recipient_map.get(cert_entity_id, [])
        results.append(cert_dict)
    return results

额外可选优化 #

如果确认每个entityid在实体表中只有1条唯一记录，可以把entity_map的值直接存单个字典而非列表，挂载的时候直接赋值不用取列表，进一步节省内存和取值时间。

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