Python Tuple键字典整批匹配条目高效检索方案咨询

问题1：部分键检索的时间复杂度 #

你当前使用的原生字典+列表推导式的实现，时间复杂度是O(N)，N是字典的总条目数，和匹配到的条目数量无关。因为原生字典没有对Tuple的子元素单独建索引，要判断key[0]==2必须遍历所有键逐一校验，哪怕最后只匹配到2条，也要把全量key扫一遍。

如果想要时间复杂度和匹配条目数成正比，可以自行构建二级索引，调整存储结构为嵌套字典：

# 二级索引结构：{tuple第0位元素: {tuple第1位元素: 对应值}}
index = {
    1: {5: {'a'}},
    2: {3: {'b','c'}, 4: {'d'}}
}
# 查询第0位为2的条目，直接取内层字典即可，无需遍历全量数据
match_items = index.get(2, {}).items()
# 统计逻辑可以直接基于内层字典执行，效率更高
sum(len(val) for val in index.get(2, {}).values())

这种结构下完整键查询也保持O(1)效率：index[key0][key1]，和原生Tuple键字典性能一致，部分键查询直接跳转到对应分组，时间仅和匹配到的条目数量正相关。

问题2：和pandas groupby方案的性能对比 #

两者优劣分场景判断：

• 中小规模数据集（万级条目以内）、查询量少、不需要其他表格操作的场景：Tuple键字典+列表推导的方案性能更好。pandas构造DataFrame、执行groupby都有额外的调用开销，小数据量下这个开销占比很高，纯Python字典方案内存占比仅为pandas的1/3~1/2，查询速度也快30%以上。
• 大规模数据集（十万级条目以上）、需要多维度聚合、批量统计的场景：pandas方案性能更好。列表推导本质是Python层的循环，数据量上来之后Python循环的效率远低于pandas底层的向量化C操作，哪怕内存占用更高，整体执行速度会比纯Python字典遍历快数倍。

如果你的查询频次很高，优先选择加了二级索引的字典方案，不管是内存占用还是查询延迟都远优于pandas。

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