Python 3.8中如何优化字典列表包含关系校验的实现算法

你当前的实现时间复杂度为O(mn)*，其中m是待校验列表的长度，n是参考列表的长度，当参考列表数据量较大时性能会明显下降，可通过哈希结构优化查找效率。

优化思路 #

核心是将参考列表的查找复杂度从O(n)降到O(1)：

• 先遍历一次参考列表，将其转换为「演员名：参演电影集合」的映射字典，电影转集合是为了后续的包含判断也能做到O(1)
• 再遍历待校验列表，直接通过哈希表查询校验即可

优化后代码 #

from typing import List, Dict, Set

def isContained(l1: List[Dict[str, List]], l_final: List[Dict[str, List]]) -> bool:
    # 预处理参考列表生成映射结构，仅需遍历一次
    final_map: Dict[str, Set[str]] = {}
    for item in l_final:
        final_map[item['name']] = set(item['films'])
    
    # 逐个校验待校验列表的元素
    for elem in l1:
        name = elem['name']
        # 演员不存在直接返回不包含
        if name not in final_map:
            return False
        # 校验所有电影都在对应演员的电影列表中
        if not set(elem['films']).issubset(final_map[name]):
            return False
    return True

如果待校验的单条电影数量很少，也可以不用转小集合，直接用遍历判断节省开销：

# 将上面的集合包含判断替换为以下代码
if not all(film in final_map[name] for film in elem['films']):

验证结果 #

运行你给出的测试用例，输出和原代码完全一致：

True
False
True
False

复杂度说明 #

优化后整体时间复杂度为O(n + mk)*，其中n是参考列表长度，m是待校验列表长度，k是待校验列表单条数据的电影数量，远优于原实现的时间复杂度，数据量越大优化效果越明显。

内容的提问来源于stack exchange，提问作者Aurélien BOUDIER