面试题：Python字典列表在多场景下的高效算法优化

Question

给定一个非常大的Python字典列表，每个字典都有'id'（唯一标识）、'category'（类别）和'value'（数值）等多个键值对。现在有两个需求：1. 快速统计每个类别下所有字典'value'的总和；2. 实现一个高效的查询功能，能够根据输入的'id'快速定位到对应的字典。请设计并实现这两个功能，同时考虑如何优化性能以应对大数据量。

Answer 1

from collections import defaultdict


def sum_values_by_category(data):
    category_sum = defaultdict(int)
    for item in data:
        category_sum[item['category']] += item['value']
    return category_sum


def find_dict_by_id(data, target_id):
    id_dict = {item['id']: item for item in data}
    return id_dict.get(target_id)


# 示例数据
large_data = [
    {'id': 1, 'category': 'A', 'value': 10},
    {'id': 2, 'category': 'B', 'value': 20},
    {'id': 3, 'category': 'A', 'value': 30}
]

category_sums = sum_values_by_category(large_data)
print("每个类别下所有字典'value'的总和:", category_sums)

found_dict = find_dict_by_id(large_data, 2)
print("根据'id' 2定位到的字典:", found_dict)

性能优化说明

1. 统计每个类别下所有字典'value'的总和：
   • 使用defaultdict(int)来存储每个类别的总和。defaultdict在访问不存在的键时会自动创建一个默认值（这里是0），这样在累加时无需手动检查键是否存在，提高了代码简洁性和执行效率。
   • 遍历一次字典列表，时间复杂度为$O(n)$，$n$是字典列表的长度，这是在这种情况下能达到的最优时间复杂度。
2. 根据输入的'id'快速定位到对应的字典：
   • 构建一个以'id'为键，字典本身为值的新字典。在构建过程中遍历一次字典列表，时间复杂度为$O(n)$。
   • 之后根据'id'查询时，字典的查找操作平均时间复杂度为$O(1)$，相比遍历整个列表查找（时间复杂度为$O(n)$），大大提高了查询效率。