外观
日志去重与分组该选什么:list、tuple、dict、set 的用法与实现
摘要
日志量增加后,去重越来越慢,常见原因是把列表用于重复成员搜索。本文面向 Python 初学者,从去重与分组出发解释四类容器,连接使用方式与数组、哈希表机制,并说明复杂度和不可变性的边界。
1. 场景:同样的结果,数据规模改变后代价不同
考虑一个教学场景:日志脚本保存所有请求路径,然后用 if path not in seen_list 判断是否第一次出现。输入很小时它直观且正确;输入增长后,每次成员判断都可能扫描已经记录的路径,累计工作量迅速增加。问题不一定出在 Python 解释器“天生慢”,而是数据结构与主要访问方式不匹配。
先明确需求。你可能需要保留所有事件的顺序、按路径统计次数、仅判断路径是否已出现,或者保存一条固定结构的记录。这四件事适合不同的容器:list 是可变序列,tuple 是不可变序列,dict 是键到值的映射,set 是不重复元素的集合。sequence(序列)以位置组织元素,mapping(映射)以键关联值。不要因为都能用 for 遍历就认为其访问代价和语义相同。
选择容器还要说明是否要求保序。列表和元组有位置顺序;字典从 Python 3.7 起具有语言层面的插入顺序保证。集合不提供这样的业务顺序保证,不能依赖某次运行中看到的顺序输出报表。即使特定运行内迭代看起来稳定,也不是跨运行、跨构造过程都适用的排序规则。字典顺序与集合操作见 内置容器文档。
在挑容器之前,先固定两个判断:结果需要什么关系,执行要保存和搜索多少状态。 按位置取、保留顺序、成员判断与计数不是同一种需求。让列表和字典得到同一个去重结果,再比较它们查重的工作,才能把结果正确与成本变化分开;换一个更复杂的容器名字不构成性能证据。
2. 列表:随机访问容易,中间移动有代价
list 支持下标、切片、追加、插入、删除和排序。items[0] 获取第一个元素,负下标从末尾计数,切片终点不包含。越界的单个下标通常抛 IndexError,切片则有边界调整规则,不能把两者混为一谈。append(x) 添加一个元素;extend(values) 添加可迭代对象里的各项。把一个列表传给 append 得到嵌套列表,传给 extend 则展开这一层的元素。
CPython 列表可以理解为动态数组保存对象引用:数组位置使按下标获取引用直接,元素对象本身未必连续。容量不足时需要调整底层存储,尾部追加通常有预留空间和扩容过程;“每次追加都是绝对固定成本”并不成立。常见复杂度模型中,下标访问是常数时间,尾部追加是摊还常数时间。amortized(摊还)意味着把偶尔较贵的扩容分摊到一系列操作,而不是承诺每次操作的延迟相同。具体内存布局与扩容参数以固定版本源码为准,不在这里编造扩容比例。
在列表开头插入或删除,通常要移动后面的引用,因此随着元素数增加成本上升。成员搜索则需要逐项比较,成本取决于比较次数以及单次相等判断的代价。若元素的 == 本身做复杂计算,不能仅说“扫描了几次”就估计真实时间。用于频繁头部取出任务时,可以考虑 collections.deque 双端队列;不要把 list.pop(0) 当成适合所有规模的队列实现。
原地修改方法通常返回 None,例如 list.sort()。sorted(values) 则返回新的排序列表。items = items.sort() 会把变量绑定到 None,后续代码因此失败。这是具体接口语义,不是所有修改方法的统一承诺:pop() 就返回被移除的元素。官方教程列出各方法行为,见 数据结构教程。
3. 元组:固定引用集合,不代表整个对象图冻结
tuple 经常用于一条固定结构记录,例如 ("/orders", 500)。创建单元素元组需要逗号:("/orders",);仅加括号 ("/orders") 仍是字符串。解包能把记录的字段绑定到名称,path, status = event 要求数量对应。字段较多时按位置记忆容易出错,后续可以引入命名元组或数据类,让字段名称参与接口表达。
元组不能通过 record[0] = ... 替换元素引用,但可以包含可变对象。record = ("/orders", []) 后执行 record[1].append(500) 是允许的:元组里的第二个引用没有改变,那个列表的状态变了。第三篇已经建立对象图模型,这里把它用于容器选择。官方数据模型也明确区分不可变容器与它引用的可变对象,不应把“tuple”翻译成“绝对只读的数据”。
哈希键的选择同样不能只看最外层类型。tuple 是否可哈希取决于其元素是否可哈希。含列表的元组不能作为普通字典键。hashable(可哈希)对象提供生命周期内稳定的哈希值,并满足相等对象具有相同哈希值的约束。不可变是理解常见内置键的好线索,但不是一般对象的完整定义;自定义实例可以按身份可哈希,也可以因相等性定义失去默认哈希能力。 可进一步阅读Hash表原理与工程应用:哈希碰撞与复杂度条件有独立推导。
4. 字典和集合:哈希缩小搜索,比较确认结果
哈希函数把键映射为整数,哈希表根据该值选择候选位置,再用身份或相等性确认是不是目标键。不同键可能有同样哈希值,这叫 collision(哈希冲突),所以哈希值相同不代表键相等。平均情况下,合理的哈希分布使字典和集合的成员查询不必逐项扫描;但极端冲突、昂贵哈希和昂贵相等比较仍可能改变成本。不能把平均常数时间当成任何输入都恒定时间。
CPython 的字典实现涉及索引存储和条目存储,集合也有自己的哈希表布局;二者都需要管理空位置、删除痕迹与扩容,细节并不是完全相同。底层核心问题是怎样在冲突发生时继续查找,怎样保证删除后不破坏其他键的搜索路径,怎样在规模变化时重新组织表。固定 v3.14.0 源码入口列在文末,具体布局如未逐项核验,不应凭旧版本图示宣称完全一致。
字典 d[key] 在不存在时抛 KeyError,d.get(key, default) 返回默认值但不自动插入键。统计次数可以写 counts[path] = counts.get(path, 0) + 1。这表达“旧次数加一”,适合本篇单线程实验;并发环境下它是多个业务步骤,不能因为底层字典查找安全就当成整体原子操作。第十九篇会解释共享状态和锁。
集合适合成员判断、去重、并集、交集和差集。set() 创建空集合,{} 创建空字典;{"/orders"} 是非空集合字面量。想既去重又保留首次出现顺序,可以按明确的字典插入顺序规则使用 list(dict.fromkeys(paths)),或者显式维护集合和输出列表。不要把 list(set(paths)) 当成有序去重方案。
图表将在阅读到此处时加载…
这是机制示意,不是宣称所有 Python 实现使用完全相同的探测步骤。比较中还可能执行用户代码,源码分析与性能测试应固定运行时和对象类型。
图中的未使用空槽与删除标记不能混同。在 CPython v3.14.0 字典的这条探测路径中,遇到未使用槽可以判断键不存在;删除后留下的标记却需要继续搜索,否则可能错过发生冲突后放到后续位置的键。这个区别也解释了为什么删除不能简单把当前位置变成从未使用的空槽。
5. 最小实战:统计、去重与错误删除
沿同一批路径先预测三个不同目标:计数仍保留 /orders 的两次出现,去重只保留一个键,过滤则完全去掉目标路径。若把去重集合当计数表,已经改变了问题。整数去重实验固定相同顺序的输出:列表反例扫描已接受键,字典正例建立键表,断言先保证结果一致,计数才比较确定的工作。
完整程序在 04_containers.py:
python
"""固定顺序输出;集合仅用于成员判断,不依赖迭代顺序。"""
def main():
events = [("/orders", 500), ("/health", 200), ("/orders", 200)]
paths = [path for path, _ in events]
unique = set(paths)
counts = {}
for path in paths:
counts[path] = counts.get(path, 0) + 1
assert counts == {"/orders": 2, "/health": 1}
assert "/health" in unique
# tuple 的不可变性只约束它保存的引用。
record = ("/orders", [])
record[1].append(500)
assert record == ("/orders", [500])
try:
hash(record)
except TypeError:
print("unhashable tuple member")
bad = ["/orders", "/orders", "/health"]
# 遍历时原地删除会跳过元素。
for path in bad:
if path == "/orders":
bad.remove(path)
good = [path for path in paths if path != "/orders"]
assert bad == ["/orders", "/health"] and good == ["/health"]
# 比较确定的搜索工作,不把一次计时当作普遍性能结论。
inputs = list(range(100)) + list(range(100))
slow = []
comparisons = 0
for value in inputs:
exists = False
for known in slow:
comparisons += 1
if known == value:
exists = True
break
if not exists:
slow.append(value)
fast = list(dict.fromkeys(inputs)) # 保留首次出现的顺序。
assert slow == fast == list(range(100))
assert comparisons == 10000
print("dedup input/keys/list comparisons:", len(inputs), len(fast), comparisons)
print("counts:", counts)
print("filter:", bad, good)
if __name__ == "__main__":
main()执行 python docs/python/examples/04_containers.py,预期打印 unhashable tuple member,统计为 {'/orders': 2, '/health': 1},过滤反例保留一个 /orders,正例仅保留 /health。集合不直接打印顺序,避免引入无关的非确定性。列表推导式 [表达式 for 项 in 来源 if 条件] 是构造新列表的语法;它仍分配结果列表,不是自动流式处理。
删除反例中,第一个 /orders 被移除,第二个移动到零号位置;遍历位置继续向前,因此它被跳过。正例读取原列表,另建符合条件的列表,让遍历来源与结果互不干扰。如果必须保留原列表对象身份,可以计算新结果后用切片赋值替换内容,但这会被所有共享该列表的引用观察到,需要结合第三篇的所有权模型判断是否允许。
6. 容器选择要同时考虑规模和寿命
成员判断从列表改成集合,通常是访问模型改善,但集合也有表空间和哈希计算成本。三条记录时无法据此断言实际运行更快;大量记录时也应结合键长度、重复率和内存预算测量。复杂度描述增长趋势,性能测试描述特定条件的实际耗时,二者互相解释但不互相替代。后续性能篇会提供可复现的比较方法。
按路径聚合还有一个常被忽略的坑:键的种类可能无限增长。如果日志路径含用户 ID、订单 ID 或查询参数,counts[path] 的键数量可能接近请求数量,脚本内存持续增长。修复不能只换一个“更快字典”,而要定义路由模板、时间窗口和最大基数。cardinality(基数)是不同键的数量;聚合容器的空间与它直接相关。是否丢弃、分桶或分批落盘,应由统计需求决定。
选择键时也检查规范化。/orders 与 /orders/ 是否相同,需要业务规定;大小写、编码和查询参数不能随意删掉。过度合并会损失区分信息,不合并可能使基数爆炸。正确顺序是先明确统计维度,再选择容器和键表示,然后设置可观察的资源边界。
嵌套容器会影响真实内存口径。sys.getsizeof 给出对象自身占用相关信息,不自动递归统计它引用的全部对象。一个列表很小,内部可能保存巨大字符串;两个容器共享子对象,直接把递归大小相加又可能重复计算。第十八篇会进一步讨论对象图与内存分配,这里避免用单一大小函数证明整段业务数据的真实内存成本。
7. 再看哈希键:稳定性是正确性的条件
假设用可变业务对象作为键,并把哈希值定义为某个可变字段的哈希。对象插入后修改该字段,下次查找可能从另一个候选位置开始,找不到原条目。即使字典仍然持有对象,搜索路径也不再符合插入时的假设。不是字典“把键丢了”,而是键违反了稳定哈希的协议。解决方式是使用稳定标识,或明确建立不可变键表示,而不是插入后每次修改都重试查找。
相等性与哈希也必须一致。两个对象若 == 为真,其哈希值应相同;反过来,哈希相同的对象仍可以不相等。哈希表用后续相等检查处理冲突,所以不能把 hash(x) 直接当成唯一业务 ID。跨进程持久化也不应依赖内置 hash:字符串等类型的哈希受随机化设置影响,不适合成为固定的文件格式或跨服务签名。需要稳定摘要时选择符合协议的算法,并说明碰撞与安全条件。
内置数值还体现相等键的影响:True 与整数一相等,通常会指向同一字典键位置语义,不能把布尔值和整数混用后期待它们是两个独立统计维度。如果接口允许多种来源类型,应在构造键前规范化并验证,必要时加入明确的类型标签。问题来自相等性协议,不是字典打印省略了某个值。
字典访问的“键不存在”与“值为 None”也不同。get(key) 默认返回 None,若 None 是合法保存值,就无法仅凭结果判断键是否存在。可以使用 key in mapping,或带专用哨兵的 get。不过如果并发修改同时存在,先判断再读取仍是两个步骤,需要额外业务同步。本篇实验只有单线程静态输入,不把这种组合当并发安全保证。
setdefault(key, default) 会在缺失时插入默认对象,但默认实参表达式在调用前已经求值,不能假设键存在就不创建它。defaultdict 的工厂通常在特定缺失访问时调用,语义又不同。对普通计数直接使用 get 很清楚;对列表分组可以根据创建成本与接口需求选工具。更短的写法可能隐藏对象创建时机,读者应先能解释过程再采用。
8. 容器变化为什么影响遍历和视图
字典的 keys()、values()、items() 返回相应视图,通常观察原字典而不是立即复制所有条目。view(视图)表达的是关联观察关系;字典变化后视图内容也可能变化。想获得独立的这一层快照可以构造列表,但内部值仍共享。第三篇对象模型在这里继续适用,不因为调用了 items() 就自动冻结全部数据。
遍历字典时增删键,可能抛运行时错误或造成无法依赖的观察,不适合设计为通用批量修改方式。若需要删除满足条件的键,先确定待删键列表,再单独删除,或者构造新字典。只更新已有键的值与改变键集合不同,但业务也要说明遍历时是否允许观察更新。没有同步的并发迭代不能以“本次没报错”证明一致性。
排序是额外的处理阶段。sorted(counts.items(), key=lambda item: item[1], reverse=True) 可以按次数生成新列表;同次数如何排序应明确,否则不同输入插入顺序可能产生不同报告。若要求稳定可比的文本输出,可设置次数和路径的复合排序键。排序结果并不会让原字典变成按该顺序重新定义的映射,下一次更新也不会自动维持名次。
删除与缩小内存之间同样没有简单对应。容器可能保留容量供后续复用,子对象可能仍被其他引用持有,进程分配器也可能暂不归还页面。移除一万个键后 RSS 不立即下降,不足以证明这些键还在字典里;要分别检查逻辑条目数、对象保留路径和进程内存口径。这个区别在第十八和二十三篇会成为排障主线。
9. 用工作量设计一份可信比较
若要比较列表与集合去重,先固定同一输入,确保两种实现得到相同成员集合,若要求保序也必须满足同样顺序。随后明确是否把构造容器的时间算进去。只测已经建好的集合查询,再与包含建立列表的流程比较,会把准备成本不对称地排除。读多写少和只查询一次的工作负载,可能有不同最合适选择。
至少控制总记录数、不同路径数、键长度和命中率。完全重复的短键与几乎全不同的长键,对内存和哈希工作量不同。测量需要重复、记录运行时与硬件,并关注波动;本篇没有声称任何提升百分比。能用复杂度解释增长趋势,再用测量说明真实成本,才是一份可用于工程判断的结论。
同时检查空间预算。集合与字典为了查询效率通常需要额外表结构,不能只比较容器保存的元素数。对一次性的小数据处理,列表的直观语义可能足够;对长期聚合,键基数与时间窗口往往比单次查询速度更重要。选择数据结构不是比赛谁“级别更高”,而是把数据访问、资源预算和交付语义放在同一个模型里。
10. 面试追问:解释条件,比背 O(1) 更重要
为什么字典查询通常比列表成员搜索更适合大规模去重? 哈希缩小候选范围,列表通常逐项比较;接着说明哈希冲突、键计算代价与内存权衡。回答“字典永远 O(1)”漏掉了成立条件。
元组都能作为字典键吗? 不能,元素也要满足可哈希要求。举出含列表的元组即可,再说明不可变容器并不冻结可变元素。
字典保序是否等于自动排序? 不是。插入顺序反映键加入的过程,不按字母或数值排序。更新已有键的值不自动改变为最新排序;如果报表要求排序,需要显式 sorted 并说明排序键。
从去重迁移到长期统计:成本看输入量与键数
把一次去重改成长时间日志计数,查找方式可以沿用,状态寿命却变了。即使平均查找工作可控,保存的键仍可能随唯一路径增长。先问 n 影响读取多少次,再问 k 影响保留多少项,最后检查何时清空;第二十二篇补测量,十八篇补对象保留,这两步不能由一次去重计时代替。
增强实验把一百个不同整数重复两轮,共二百条输入。反例逐项扫描已接受列表,计数每一次显式相等比较,得到一万次;正例 dict.fromkeys 对相同输入保留首次出现顺序,结果完全一致,唯一键数为一百。这里的一万是本段循环的确定计数,不是运行时秒数,也不是对字典比较次数的猜测。字典路径仍需要计算哈希、处理冲突、可能扩容,不能把二百次输入处理说成二百条机器指令。
若输入长度为 n,不同键数为 k,朴素列表查重通常需要与越来越大的已接受列表比较,最坏会达到 O(nk),全异时可成为 O(n²)。哈希稳定、计算代价可控、冲突分布正常时,字典或集合通常有平均 O(n) 总查找工作,但要额外保存 O(k) 项状态;恶意或极端碰撞会破坏正常平均条件。整数只是教学键,长文本、复合键、定制 __eq__ 的成本还需另算。去重结果需要顺序才选字典;只要成员判断时集合也合适。
独立练习:把同一实验分为全同、全异、重复热点三种输入,记录 n、k、显式比较次数和输出顺序。验收:两种方法结果一致;全异列表计数为 n(n-1)/2;不得写“永远快一百倍”。若要性能报告,接着用第二十二篇的方法做重复测量。若状态一直累积,再看第十八篇,容器选型不能代替容量与生命周期管理。
一句话总结:按主要访问方式选容器,再检查顺序、哈希条件和数据规模,才能同时保证语义与成本。
- 列表适合有序序列,字典适合映射统计,集合适合成员判断,元组适合固定引用结构。
- 哈希表的平均复杂度有条件,扩容、冲突与对象比较影响实际代价。
- 不可变、可哈希和整个对象图只读是不同性质,容器选择还要限制聚合基数。
参考:数据结构教程、字典和集合、数据模型。源码入口:listobject.c、dictobject.c、setobject.c;本篇不以未核验的具体扩容常数作结论。独立示例已在 Windows x64 的 CPython 3.14.0 和 3.13.7 验证通过。
上一篇:对象引用与可变性。下一篇:函数参数作用域与闭包。延伸:性能测量与热点分析。