Python合并嵌套字典重复USERID条目 求高效优化方案

当前使用的双重循环Combiner函数时间复杂度为O(n²)，处理1万条数据时会产生1亿次循环，导致效率极低且内存占用过高。下面是基于字典分组的O(n)时间复杂度优化方案：

核心思路 #

使用字典以USERID为键，直接遍历原始列表一次，将同一用户的BATCH和ITEMS值逐步整合到对应的列表中，最后将字典的值转换为列表即可得到合并结果。这种方法仅需遍历数据一次，字典查找的平均时间复杂度为O(1)，整体效率远超原方案。

优化代码 #

def merge_user_entries(raw):
    user_groups = {}
    for entry in raw:
        user_id = entry['USERID']
        batch = entry['BATCH']
        items = entry['ITEMS']
        
        if user_id not in user_groups:
            # 首次遇到该用户，初始化合并条目
            user_groups[user_id] = {
                'USERID': user_id,
                'BATCH': [batch],
                'ITEMS': [items]
            }
        else:
            # 已有该用户，追加BATCH和ITEMS值
            user_groups[user_id]['BATCH'].append(batch)
            user_groups[user_id]['ITEMS'].append(items)
    
    # 将字典中的合并结果转换为列表
    return list(user_groups.values())

使用示例 #

# 原始输入数据
raw = [
    {'USERID': 'USERID1', 'BATCH': 'NUM1304', 'ITEMS': '105'}, 
    {'USERID': 'USERID15', 'BATCH': 'NUM1323', 'ITEMS': '122'}, 
    {'USERID': 'USERID1', 'BATCH': 'NUM1365', 'ITEMS': '98'}, 
    {'USERID': 'USERID12', 'BATCH': 'NUM1365', 'ITEMS': '76'}, 
    {'USERID': 'USERID1', 'BATCH': 'NUM1376', 'ITEMS': '55'}, 
    {'USERID': 'USERID3', 'BATCH': 'NUM1396', 'ITEMS': '151'},  
    {'USERID': 'USERID7', 'BATCH': 'NUM1398', 'ITEMS': '69'}, 
    {'USERID': 'USERID7', 'BATCH': 'NUM1398', 'ITEMS': '126'}, 
    {'USERID': 'USERID12', 'BATCH': 'NUM1422', 'ITEMS': '76'}, 
    {'USERID': 'USERID15', 'BATCH': 'NUM1455', 'ITEMS': '77'}, 
    {'USERID': 'USERID1', 'BATCH': 'NUM1465', 'ITEMS': '97'}
]

# 执行合并
merged_result = merge_user_entries(raw)

# 输出结果
for item in merged_result:
    print(item)

输出结果 #

{'USERID': 'USERID1', 'BATCH': ['NUM1304', 'NUM1365', 'NUM1376', 'NUM1465'], 'ITEMS': ['105', '98', '55', '97']}
{'USERID': 'USERID15', 'BATCH': ['NUM1323', 'NUM1455'], 'ITEMS': ['122', '77']}
{'USERID': 'USERID12', 'BATCH': ['NUM1365', 'NUM1422'], 'ITEMS': ['76', '76']}
{'USERID': 'USERID3', 'BATCH': ['NUM1396'], 'ITEMS': ['151']}
{'USERID': 'USERID7', 'BATCH': ['NUM1398', 'NUM1398'], 'ITEMS': ['69', '126']}

额外说明 #

• 若需要对BATCH字段去重（如示例输出中USERID7的BATCH仅保留一个），可修改追加逻辑为：

  if batch not in user_groups[user_id]['BATCH']:
      user_groups[user_id]['BATCH'].append(batch)
  

• 该方案无需依赖原有的Corrector、DuplicateCombiner和DuplicateRemover函数，代码更简洁且无冗余操作。

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