Python高效去重优化：大数量级分组打分代码性能提升咨询

原代码性能瓶颈 #

• 已选列表already_chose用列表存储，in查询操作时间复杂度为O(n)，n为已选名称总数量，数据规模大时查询开销极高
• 组内去重用列表repeat实现，not in校验操作时间复杂度为O(k)，k为当前分组的元素数量，每个分组都要重复执行多次校验操作，叠加后开销巨大

优化后代码 #

group = {
    1: ["Jack", "Jones", "Mike"],
    2: ["Leo", "Theo", "Jones", "Leo"],
    3: ["Tom", "Jack"]
}
already_chose = ["Tom", "Mike"]
# 预转集合，将成员查询复杂度降到O(1)
already_chose_set = set(already_chose)
result = []
for group_id, name_list in group.items():
    # 计算x：组内去重后不在已选集合的元素数量
    unique_names = set(name_list)
    x = len(unique_names - already_chose_set)
    # 计算y：原分组中属于已选集合的元素总个数（包含重复元素）
    y = sum(1 for name in name_list if name in already_chose_set)
    score_group = x - y
    result.append([group_id, score_group])

运行输出和原代码完全一致：[[1, 1], [2, 3], [3, 0]]

优化效果说明 #

• 整体时间复杂度从原有的O(GL(A+L))降至O(G*L)，其中G为分组总数，L为单分组平均元素数，A为已选名称总数
• 针对7000分组、单分组100元素的场景，纯Python实现即可在毫秒级完成运算，无额外依赖
• 如果后续需要处理更大规模的数据，可引入pandas做向量化运算，性能会有进一步提升

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