高级数据结构与算法设计 05：怎样验证一个算法实现
一个程序跑得更快，可能只是少算了一部分答案。验证算法实现首先要确认输入输出语义相同，再比较资源成本。第 00–04 篇已经建立契约、不变量、渐近分析、摊还和期望界；本篇把这些结论对应到可复跑检查，形成后续数据结构共同使用的验证方法。
实验输入均由本地程序生成，不使用生产数据。代码只依赖 Python 标准库。正确性检查与计时分开运行：前者遇到不一致应失败，后者记录当前机器上的样本，不负责证明算法对全部输入正确。
独立参照应当独立在哪里
第 00 篇榜单按 (-score,id) 建立全序。直接把优化实现复制一份、改变量名作为参照，很容易保留同一个 bug。更合适的参照是字典保存记录、查询时排序；rank 还可用“严格位于目标之前的记录数加一”逐项计算。
先检查已知答案，再检查关系。12 条手算序列确认同分、更新、删除和 ID 不复用；对每个有效 ID，验证 select(rank(id)) 恰好返回该记录。互逆性质有用，但单独不够：如果 rank 与 select 同时采用了错误的同分顺序，它们仍可能互逆，所以还须与独立排序定义对照。
二分使用标准库 bisect_left 作参照，其输出契约是左侧全部 <x、右侧全部 >=x。Python bisect 文档 教学程序额外检查这两个分区条件，降低单纯依赖另一个实现的风险。若比较的一个函数返回元素、另一个返回插入位置，差分结果就没有意义。
一个小到能手算的失败
故意错误版本把第 01 篇的 A[mid]<x 改成 A[mid]<=x。枚举长度 0 到 7、元素取自 {0,1,2} 的非降序数组，并查询 -1 到 3。数组生成使用可重复组合，避免把本应排除的无序数组掺入验证域。
实际共执行 600 个数组/查询组合。错误版本在 [0] 查询 0 时返回 1，参照返回 0。这是按当前枚举顺序找到的第一个反例；空数组没有反例，而非空数组至少长 1，所以它的长度已经最小。不宣称它是所有可能整数编码下唯一的“最小输入”。
修复比较符号后，这 600 个实例全部一致。结论只能写成“实现通过了这个有限输入域”，一般正确性仍由第 01 篇的证明给出。有限枚举可以穷尽一个有限模型；若把模型扩大到任意长度整数数组，就没有穷尽。
变异实现保留在 lower_bound.py，函数名为 wrong_lower_bound，检查器要求它被检出。若未来有人让检查器跳过重复值，变异可能无法被发现，这正好暴露验证器覆盖面的退化。错误代码不是供业务调用的替代实现。
操作计数与时间不是同一单位
第 03 篇模拟数组复制次数，帮助核对摊还推导。模拟不执行真实内存复制，因此不能比较缓存、带宽或分配器。第 04 篇枚举散列函数参数，核对有限概率空间；它不报告外部攻击下的安全性，也不证明真实字典的运行时间。
二分比较次数应随每次区间收缩记录；若计时器测的是整批查询，里面还包含 Python 循环、函数调用与累加校验值的成本。解释器层开销可能在小输入上占主导，但这不意味着二分算法变成了常数时间。更不能把一次计时除以 log n 后接近某个数，就当作复杂度证明。
本篇基准比较教学 lower_bound 和标准库 bisect_left。两者回答相同的插入位置查询。代码先计算并比对完整结果，计时阶段遍历相同查询并累加返回下标，确认两种路径都实际消费了结果；不在计时循环里进行断言和输入生成。
可复跑的测量合同
输入为固定种子 20260919 生成的 10000 个排序整数和 2000 个查询。JSON 中记录输入的 SHA256、解释器、平台、时钟、源码校验和及原始样本。SHA256 用于辨认输入字节，不是证明随机样本具有代表性。
每种实现先预热一轮，再测量五轮，交替执行次序以减轻固定先后顺序的影响。每个样本表示一批 2000 次查询的总纳秒数。只有一个进程和一份固定输入，没有跨机器、跨进程或 CPU 隔离实验；交替顺序也无法消除全部系统噪声。
Python timeit 文档提醒小片段计时的执行环境及重复测量会影响解释。本实验直接使用高精度计时器，明确保留全部样本，而不套用一个未执行的 timeit 默认设置。Python timeit 文档
1 | |
不要加 -O，因为检查脚本用 assert 验证结果，Python 优化模式会移除断言。保存本次真实输出可以使用：
1 | |
第一个命令失败时不应继续宣称性能比较有效。也不应仅保留最快一轮、删除其他样本；原始结果让后续读者能够判断波动与所选统计量的关系。
已运行结果及其限度
保存的测量来自 CPython 3.14.4、macOS arm64，输入校验和为 81454b716ed2dccccb46fcad315464d8a362f1729892587717116fa06e00de3c。教学二分五轮批次纳秒数为 1084292, 1060833, 1049917, 1185542, 1136750；标准库为 269667, 259125, 249000, 278625, 295083。两种实现的结果校验和均为 9874080。
这份固定样本中，标准库实现的批次耗时更低。结论只针对记录的程序、平台和输入，不能归因于渐近阶不同：两个算法都执行对数级查找。也不能据此推断第 06 篇有序树在高更新负载下的表现，本实验根本没有更新。
重跑的时间数值通常变化；输入与输出校验和应保持一致。若代码被修改，源码校验和也应改变，应同时保存新结果，不能让旧样本冒充新实现的证据。本文下载附件测量与核对说明帮助辨别计时口径，完整原始文件以本地仓库 results/ 为准。
怎样扩展到后续章节
后续每个结构先复用榜单契约或显式声明新操作，再选择独立参照。例如旋转后的树要核对顺序、平衡和子树计数，区间求和用逐项扫描，历史版本用朴素快照。参照很慢可以接受，因为它只运行在受控小实例上；参照与被测实现共享复杂逻辑则会削弱价值。
性能实验应扩展规模、重复比例、更新比例和查询分布，每组仍先验证结果。若是近似算法，还必须记录质量指标；若是概率结构，先区分已插入与未插入对象。没有这些条件的“平均耗时”，无法说明付出了什么误差或漏检代价。
- 把二分变异改为
lo=mid。构造导致不终止的输入，为检查器加入基于区间长度的有限步数约束，使失败能被报告而不无限等待。解释步数约束为什么需要从终止性证明得到。 - 保持查询语义不变，将基准输入扩展为三个 n 与两种重复程度，每组至少五轮并保留原始样本。先验证全部返回值，再解释结果是否足以支持“某实现永远更快”。指出仍未覆盖的环境变量。
参考资料
- Python bisect，作为独立参照的插入点语义。
- Python timeit，重复计时及环境影响；本文的执行代码和记录方式另行明确，不冒充文档示例结果。
