结构组合、容量边界与性能诊断
本节目标
把前九节从“容器知识”转成工程决策：根据主要操作、规模、顺序、可变性和容量选择结构；组合多个结构时写单一更新入口和不变量；性能异常时先用证据定位。
结构选择卡
每个状态组件至少回答：
| 维度 | 问题 |
|---|---|
| 主操作 | 追加、按键查找、成员判断、取最小、邻居遍历分别多频繁？ |
| 规模 | 当前与一年后的节点/事件/字节数？边数如何增长？ |
| 顺序 | 插入顺序、排序、FIFO、优先级还是无顺序？ |
| 重复 | 允许重复、计数、去重还是业务幂等？ |
| 可变性 | 谁拥有对象？快照还是共享引用？ |
| 容量 | 有无上限、淘汰、背压和溢出行为？ |
| 持久性 | 进程重启后是否必须保留？ |
| 并发 | 单线程、多个协程、线程、进程还是多机？ |
| 确定性 | 是否需要重放、审计或稳定测试输出？ |
只有回答这些问题，复杂度表才有意义。
常见 Agent 场景映射
| 场景 | 主要结构 | 关键边界 |
|---|---|---|
| 对话消息顺序 | list | 上下文容量、快照与敏感内容 |
| 最近 N 条延迟 | deque(maxlen=N) | 淘汰不等于审计保存 |
| 工具名查定义 | dict | 名称唯一、权限索引一致 |
| 已处理调用 ID | set | 进程内去重不等于持久幂等 |
| 错误分类计数 | Counter | 时间窗口与标签基数 |
| 小型时间边界 | 已排序 list + bisect | 插入仍为 ，并发修改风险 |
| 当前 ready 任务 | heapq | 平局、饥饿、惰性删除 |
| 步骤依赖 | 邻接表 + 入度 | 缺节点、环、方向约定 |
向量检索不是“把 embedding 放进普通 list 后线性扫描”就完成；专门索引、过滤、持久化和召回权衡属于 向量数据库。
多结构组合要有单一真相源
任务调度器可能同时维护：
by_id: task_id → Task # 真相源
dependents: predecessor → children # 派生索引
remaining: task_id → int # 派生计数
ready: heap # 当前可执行视图若每层都能被外部随意修改，就会出现“字典有任务但入度表缺项”。把构建和更新收进一个模块；派生索引能重建时要说明重建方式。常见不变量：
- 四个结构引用的任务 ID 都属于
by_id； remaining[id]等于尚未完成前驱数且不为负；- ready 中只有
remaining == 0且未完成的有效任务； - 同一有效任务最多有一个当前 heap entry，或使用版本标识跳过旧条目。
容量不是“以后再说”
无界列表、集合和字典会随运行时间增长。设计时确定：
- 最大条目数、字节数、深度或边数；
- 达到上限后拒绝、淘汰、采样、持久化还是背压；
- 淘汰是否影响审计、幂等或恢复；
- 低基数字段和高基数 ID 分别怎样观测；
- 清理操作本身的复杂度与并发语义。
有界 deque(maxlen=N) 满时会从新增操作的相反端静默丢弃元素；只有始终用 append 按时间追加时，左端被丢弃项才是最旧项。它适合明确约定方向的窗口，不适合需要显式告警的关键队列。
性能诊断顺序
- 明确用户可观察症状和预算；
- 记录输入规模、操作频率、Python/依赖版本和环境；
- 用 profiler、
timeit、tracemalloc或指标找到实际热点； - 判断瓶颈是算法增长、对象分配、I/O、锁还是外部服务；
- 只替换热点结构，保留正确性和回归测试；
- 用相同工作负载复测，并记录代价（内存、复杂性、可维护性）。
不要看到双层循环就直接改，也不要凭一次微基准把整个系统换成复杂结构。对 Agent 系统，模型/API 等待常比本地容器操作大，但这不能成为无界内存或 扫描的借口。
确定性与重放
集合顺序、同层拓扑节点和平级堆任务若没有规则，输出可能随构建顺序变化。需要重放时：
- 使用稳定唯一 ID；
- 为平局定义序号或排序键；
- 不依赖 set 迭代顺序；
- 记录结构输入版本和规则；
- 测试相同输入多次输出逐项一致。
确定性不等于正确性，但能降低调试和审计成本。
综合练习：决策表
为以下 8 个场景填写“主要操作→候选结构→时间/空间模型→顺序/容量风险→替代方案”：消息历史、工具注册、最近错误、幂等记录、ready 任务、依赖图、日志时间窗口、文档块流。
然后选择一个组合（list+set 或 graph+heap）：
- 写唯一公开更新函数；
- 写 4 条不变量；
- 制造一次只更新其中一个结构的 bug；
- 用测试捕获；
- 给出重建派生索引的方法。
自测
- 能从操作与规模出发，而不是从熟悉的容器出发。
- 能区分真相源、派生索引和缓存。
- 能为无界状态给出上限及达到上限后的行为。
- 能说明多结构组合最容易破坏哪些不变量。
- 性能优化前会记录基线，优化后会用同负载复测。
- 需要重放时不会依赖 set 或未定义的平局顺序。
下一步与相关概念
- 综合项目：项目：依赖任务调度器。
- 可观测证据与容量告警进入 运行监控。
参考资料
获取日期：2026-07-14。