39 算法速度

先分析数量级和增长阶，再在目标环境测量常数与数据分布，避免只信公式或只信微基准。

学习目标

能从输入规模、操作次数和数据分布估算算法增长趋势，并说清单位与边界
能设计可重复的目标环境基准，区分增长阶、常数项、缓存和测量噪声
能用跨越拐点的样本裁决方案，并保存预测、实测、首个差异和回退依据

速度问题先问规模

本页依据 David Thomas、Andrew Hunt《程序员修炼之道：通向务实的最高境界（第2版）》，云风译，电子工业出版社，2020 年 4 月，ISBN 9787121384356 的公开中文目录，独立重构 39 算法速度。正文、代码、图示、实验和练习都是本课程重新设计的教学材料，不复制原书正文、插图或答案。

“快”不是一个脱离输入的属性。一个实现可能在一百条记录上更快，在一百万条记录上却不可接受；一次微基准可能显示函数很快，却把网络、序列化或索引构建排除在真正的用户路径之外。算法速度的第一步是估算增长，第二步是在目标环境测量，第三步才是基于阈值做裁决。

三个会误导速度判断的陷阱

从规模到裁决的五步回路

<Term def="输入规模增大时，算法操作次数或资源消耗呈现的增长趋势，如线性、对数或平方增长。">增长阶</Term>帮助我们把问题从“哪段代码更快”改成“输入变大后会怎样”。回路中的每一步都必须留下单位和拒绝条件：

输入规模：说明记录数、查询数、字节数或并发数，不能只写一个变量名。
增长阶：列出主要操作，估算它们如何随规模增加。
估算：把操作次数、成本单位和服务阈值连起来，给出可被反驳的预测。
基准：在目标环境使用真实分布、固定种子和多次重复，拆分冷启动与稳态。
裁决：比较阈值、置信范围、资源峰值和迁移成本，决定保持、替换或继续测量。

专属图示：性能结论要同时说明增长趋势、常数、阈值和回退。

39 与提示 63、64：评估级别并测试估算

本单元对应中文目录的 39 算法速度、提示 63：评估算法的级别 和 提示 64：对估算做测试。提示不是要求每次都做复杂分析，而是要求在做决定前知道自己依赖哪一个数量级和哪一个测量假设。

例如，逐项比较两个列表的成本近似为 O(n × m)；把右侧列表放入集合后查询近似为 O(n + m)。这并不自动证明集合方案更好：建集合有成本，需要额外内存，哈希分布可能改变常数，且输入规模可能永远小于拐点。先估算，再用跨越拐点的数据验证，才能把公式和实测放进同一条证据链。

<Term def="在运行前根据操作次数、输入规模、资源单位和阈值给出的可反驳预测。">估算</Term>必须写出假设。例如“十万条记录、查询五千次、目标端到端延迟低于 100 毫秒”比“应该很快”更容易验证。估算错误不是失败的终点，而是提示我们检查漏掉的常数、数据分布或资源阶段。

读懂测量：增长、常数与噪声

<Term def="在固定硬件、软件版本、数据分布和操作协议下重复运行的可比较实验。">目标环境基准</Term>要避免把环境噪声当成算法差异。记录 CPU、内存、编译设置、数据库版本、热身次数、重复次数、输入生成种子和计时边界。网络和磁盘实验还应记录外部服务状态与超时。

<Term def="两种方案的固定成本和资源实现差异；它可能让小规模样本的快慢与大规模趋势不同。">常数项</Term>不能被复杂度符号抹掉。小输入时常数可能决定用户体验，大输入时增长阶可能决定系统是否还能工作。报告中同时展示规模曲线、分位延迟、内存峰值和阶段耗时，而不是只放一个平均毫秒数。

type Result = { elapsedMs: number; heapMb: number; size: number };
 
function estimateLinear(size: number, perItemMs: number): number {
  return size * perItemMs;
}
 
function withinBudget(
  result: Result,
  maxMs: number,
  maxHeapMb: number,
): boolean {
  return result.elapsedMs <= maxMs && result.heapMb <= maxHeapMb;
}

这里的估算只声明了线性增长和每项成本，不能冒充真实基准。实际测量还要说明分配、缓存和数据读取是否包含在 elapsedMs 内；否则不同实验测到的是不同工作。

识别复杂度拐点

<Term def="两种方案因增长趋势与固定成本交叉而改变优先级的输入规模附近。">复杂度拐点</Term>比“方案 A 永远更快”更接近工程决策。找到拐点需要至少三类数据：小规模验证常数，中规模观察趋势，大规模检查阈值与资源边界。

若拐点靠近当前生产规模，就不要把选择写成抽象偏好；把规模阈值、自动切换规则和回退方案写进系统。若数据分布变化会移动拐点，监测输入规模和分布，并在越过阈值时重新触发基准，而不是等用户发现超时。

练习实验：用跨越拐点的数据做决定

Interactive lab

选择规模情境，检查裁决证据

拐点样本

输入证据

规模跨过预估拐点，线性扫描开始逼近端到端预算。

实际首差

阈值节点：应切换索引方案或触发回退。

恢复动作

把规模阈值写入监测和回归基准。

先预测规模曲线，再选择样本；异常下降也可能是测量协议出错，不要直接把它写成优化结论。

分步1 / 4

1. 写出规模、单位和阈值

定义输入规模、查询次数、目标端到端延迟、内存预算和数据分布。列出要比较的两个实现，以及你预计它们在哪个范围出现拐点。

正常、边界与单一故障证据

专属图示：正常、边界和测量故障各有不同的证据与恢复路径。

样本	唯一变化	预期判定	必存证据
正常	稳定规模、分布和目标环境	结果满足阈值，趋势符合预测	曲线、版本和输出摘要
边界	跨越预算或复杂度拐点	明确切换或拒绝，不伪造通过	阈值、分位值和资源峰值
单一故障	一个计时阶段、索引或依赖失效	首个异常处暴露并回退	失败输入、首差和恢复

独立复核者应能从输入种子、版本、命令和阈值重建基准。平均值不能遮住长尾；单次最佳运行不能代表稳定性；理论估算也不能替代端到端用户路径。若两种方案都满足阈值，选择时再比较复杂度、维护成本和回退难度，并把理由写进决策记录。

术语表

名词解释

本章出现的专业名词，用大白话再讲一遍。

增长阶: 输入规模增大时操作次数或资源消耗呈现的趋势。
估算: 根据规模、操作次数、单位成本和阈值给出的可反驳预测。
目标环境基准: 在固定硬件、软件、数据和协议下重复运行的比较实验。
常数项: 方案的固定成本和资源实现差异，可能改变小规模样本的快慢。
复杂度拐点: 两种方案因增长趋势与固定成本交叉而改变优先级的规模附近。

练习

问题 1： 两个列表各有 100 条记录时，逐项比较比建集合更快。你会如何判断是否应该换算法？

问题 2： 微基准显示排序函数更快，但端到端请求更慢。哪些证据能帮助你找到原因？

问题 3： 一次基准中大输入延迟突然下降，你会直接宣布优化成功吗？

本单元回顾

评估算法速度，先从规模和增长阶开始，再用目标环境基准测量常数、分布、长尾和资源峰值。不要让复杂度符号遮住真实成本，也不要让一次微基准替代用户路径。能说明拐点、阈值、首个差异和回退动作，才是可以迁移的性能判断。