外观
A - 算法正确性、测试与基准方法
示例环境:Java 17。JMH、属性测试框架和 JVM 诊断能力会随依赖与 JDK 版本变化,实际使用时应固定版本。
摘要
算法通过几个样例,不代表它对所有合法输入都正确;一次运行更快,也不代表输入变大后仍有优势。验证可以分成三层:先明确什么结果算正确,再检查实现是否遵守这些规则,最后测量运行成本。本文按这个顺序介绍契约、不变量、自动化测试和性能基准,并说明它们各自能提供什么证据。
1. 场景:优化后的代码更快,却偶尔返回错误结果
以订单系统统计一批任务时间区间的最大并发数为例。优化前枚举时间点,速度很慢;优化后改用扫描线,即按时间顺序处理开始和结束事件,维护当前运行的任务数。普通样例中两者结果一致,但遇到一个任务结束、另一个任务同时开始时,优化实现多算了一个并发。
如果业务采用半开区间 [start,end),任务在开始时刻计入并发,在结束时刻不再计入。例如 [1,3) 和 [3,5) 在时刻 3 不重叠。此时若逐个处理事件并更新最大值,就应先处理结束事件,再处理开始事件;反过来会短暂把两个任务都算进去。闭区间包含结束时刻,不能照搬这条规则。零时长区间是否允许、如何统计,也需要在契约中单独定义。
问题不在扫描线思想,而在验证过程缺少三个条件:
- 没有明确区间是
[start,end)还是闭区间; - 没有把半开区间下“同时刻先处理结束事件”的规则落实到状态维护中;
- 测试数据没有覆盖相同端点。
这类错误说明:测试之前必须先明确业务语义,否则两个实现即使返回相同结果,也可能一起违背需求。
2. 先写可执行契约
契约是调用方与实现之间的约定:什么输入可以接受、应返回什么结果、允许产生哪些影响。“可执行”意味着这些约定足够明确,能转换为参数校验或测试断言。测试之前先定义:
text
输入域:允许哪些值,最大规模是多少?
输出语义:返回任意合法解、唯一解,还是最优值?
边界:空输入、重复值、溢出、非法数据怎样处理?
副作用:是否允许修改输入?是否要求稳定顺序?
资源限制:时间、内存、递归深度和外部调用预算是多少?例如 Lower Bound(下界查找)的契约是:对按非递减顺序排列、非 null 的数组 a,返回最小下标 i,使得 a[i] >= target;若不存在,返回 a.length。这样,[1,2,2] 查找 2 应返回 1,空数组应返回 0。重复值允许存在,但不能返回任意一个匹配位置。
3. 用不变量解释为什么正确
循环不变量是每次进入循环时都成立的事实。证明循环正确,需要说明它在初始化时成立、每次更新后仍成立,并且循环结束时足以推出所需结果。下面是 Java 方法片段,没有独立运行入口,也没有检查数组是否有序或为 null;调用方需满足上一节的契约。
java
static int lowerBound(int[] a, int target) {
int left = 0;
int right = a.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (a[mid] < target) left = mid + 1;
else right = mid;
}
return left;
}它维护三个事实:[0,left) 的元素都小于 target,[right,a.length) 的元素都大于等于 target,答案下标始终位于 [left,right]。这里数组区间使用半开形式,答案范围则包含右端点,因为“不存在”时的答案可以是 a.length。
初始化时,左右两侧都是空区间,这些事实成立。若 a[mid] < target,有序性保证 mid 及其左侧都不可能是答案,因此令 left = mid + 1;否则,mid 已满足条件,但左侧可能有更早的位置,因此令 right = mid。两种更新都保持不变量,并严格缩短待搜索区间。循环结束时 left == right,左侧都不满足条件,从该位置开始都满足条件,所以返回的正是下界。
不同算法需要证明的事实不同。下表是寻找证明方向的提示,具体表述仍取决于实现与前提;TopK 是按某个标准选出前 K 个元素,DFS 是深度优先搜索,BFS 是广度优先搜索。
| 算法类型 | 常见不变量或证明方式 |
|---|---|
| 二分查找 | 答案始终在当前搜索区间 |
| 双指针 | 被跳过元素不可能再进入答案 |
| 堆 | 用于 TopK 筛选时,根节点是保留候选的淘汰边界 |
| DFS/BFS | 带访问标记时避免重复展开状态;无权图 BFS 按边数距离分层 |
| 贪心 | 交换论证(替换选择不使结果变差)、保持领先或反证法 |
| 动态规划 | 状态覆盖对应子问题的全部合法选择 |
| 回溯 | 递归返回后恢复到调用前状态 |
样例只能检查具体输入,不能替代对这些事实的说明。
4. 暴力基线不是废代码
暴力基线是优先保证规则直观、便于检查的参考实现,通常通过枚举候选得到结果。例如判断数组中是否存在重复值,可以比较所有不同位置的元素对,再用它校验哈希集合实现。以下两个 Java 方法片段都要求输入数组非 null。
java
static boolean duplicateByPair(int[] values) {
for (int i = 0; i < values.length; i++)
for (int j = i + 1; j < values.length; j++)
if (values[i] == values[j]) return true;
return false;
}
static boolean duplicateByHash(int[] values) {
java.util.Set<Integer> seen = new java.util.HashSet<>();
for (int value : values) if (!seen.add(value)) return true;
return false;
}逐对比较在最坏情况下需要平方级的比较次数,不适合生产大输入,却适合校验几十个元素的随机样本。哈希集合实现则逐个插入元素:add 返回 false 表示该值已经存在。基线也需要按契约审查,不能因为它写得简单就自动视为正确答案。
5. 差分测试:让两个实现互相审计
差分测试让不同实现处理同一输入,再比较结果。下面的完整类使用 Java 17 标准库,源文件应命名为 DifferentialTestDemo.java。它把上一节的两种方法放入同一个测试入口,测试范围如下。
java
import java.util.Arrays;
import java.util.Random;
public class DifferentialTestDemo {
static boolean slow(int[] a) {
for (int i = 0; i < a.length; i++)
for (int j = i + 1; j < a.length; j++)
if (a[i] == a[j]) return true;
return false;
}
static boolean fast(int[] a) {
java.util.Set<Integer> seen = new java.util.HashSet<>();
for (int value : a) if (!seen.add(value)) return true;
return false;
}
public static void main(String[] args) {
long seed = 20260930L;
Random random = new Random(seed);
for (int round = 0; round < 100_000; round++) {
int[] input = new int[random.nextInt(20)];
for (int i = 0; i < input.length; i++) input[i] = random.nextInt(11) - 5;
boolean expected = slow(input);
boolean actual = fast(input);
if (expected != actual) {
throw new AssertionError(
"seed=" + seed + ", round=" + round + ", input=" + Arrays.toString(input)
);
}
}
System.out.println("all cases passed, seed=" + seed);
}
}程序生成 100_000 组数组,每组长度为 0 到 19,元素值为 -5 到 5。这个小值域容易产生重复值,短数组又能限制暴力比较的成本。结果不一致时,断言错误会记录种子、轮次和输入;全部一致时,预期打印 all cases passed, seed=20260930。
随机种子是伪随机数生成器的初始状态。固定种子并保持数据生成方式和调用顺序一致,才能重放同一批输入。两个实现应尽量避免共享关键判断,否则可能犯同样的错。即使这批测试全部通过,也只能说明在这些样本上结果一致,不能证明所有合法输入都正确;大数组、极值和指定边界仍需单独覆盖。
6. 性质测试:没有唯一答案时验证什么
性质测试检查输出必须满足的约束,而不是只与某个固定答案比较。它适用于多解问题,也适用于有唯一答案的问题。例如排序结果应满足:
- 输出非递减;
- 输出与输入包含相同元素及重复次数;
- 若要求稳定,相等元素的原相对顺序不变。
第二条防止实现通过丢掉元素来得到“有序”结果;第三条中的稳定性,是指排序键相等的记录仍按原来的相对顺序排列,只有契约要求稳定时才需要检查。
图路径可验证起终点是否正确、相邻节点之间是否有边、报告成本是否等于路径边权之和;若要求最优路径,还可在小图上与暴力枚举的最优值比较。两条路径成本相同,并不要求节点序列完全一致。只检查长度或成本,也可能漏掉路径本身不合法的问题。
7. 从算法假设设计边界测试
| 假设 | 必测输入 |
|---|---|
| 数据有序 | 未排序输入是拒绝、排序副本还是结果未定义 |
| 值均为正数 | 0、负数,以及剪枝是否仍成立 |
| 使用 int 累加 | 接近 Integer.MAX_VALUE 的值 |
| 字符按用户感知字符处理 | Emoji、组合字符、规范化差异 |
| 图没有环 | 自环、双向边、重复边和循环依赖 |
| Hash 分布均匀 | 大量冲突和恶意 Key |
| 递归深度较小 | 极端退化树或长链 |
这些输入用于检查前提的边界或前提被破坏时的处理方式,不一定都属于合法输入。例如二分查找依赖有序性:若传入乱序数组,预期行为应由契约决定,不能仍要求它给出有序输入下的结果。用户感知字符也不一定等于单个 Java char;例如字母与组合重音标记可以共同呈现为一个字符,规范化差异则可能让看起来相同的文本具有不同编码序列。
8. 复杂度验证:观察增长,而不是只看一次耗时
O(n) 描述成本随输入规模 n 增长的渐近上界,不是某次运行的毫秒数。若分析认为算法是线性增长,应测量多个数量级和多种数据分布,例如 1,000、10,000、100,000、1,000,000。这些是建议的输入规模,不是已测记录。
重点观察 n 扩大 10 倍时,比较或迭代次数怎样变化,再看耗时与内存分配。实际经过的时间称为墙钟耗时,它还受调度、垃圾回收(GC,回收不再使用的对象)和缓存命中情况影响。因此,耗时曲线不能证明 Big O,却可以提示隐藏的线性扫描、重复复制或退化输入,帮助回头检查复杂度分析。测试还应区分最好、平均和最坏情况的数据分布。
9. 用 JMH 测 Java 微基准
微基准测量一个方法或一小段代码的运行成本。JMH(Java Microbenchmark Harness)是 Java 微基准工具,用来组织预热、重复测量和独立进程运行,减少 JVM 运行机制对比较结果的干扰。
下面只展示结构,省略了 JMH 注解导入和构建配置,不能作为独立源文件直接运行。实际运行需要固定 JMH 依赖版本和注解处理器;注解处理器会在编译时生成基准运行所需的代码。
java
@State(Scope.Thread)
public class SearchBenchmark {
@Param({ "1000", "10000", "100000" })
int size;
int[] sorted;
@Setup
public void setup() {
sorted = java.util.stream.IntStream.range(0, size).toArray();
}
@Benchmark
public int binarySearch() {
return java.util.Arrays.binarySearch(sorted, size - 1);
}
}@Param 指定待测规模,@Setup 在测量前准备有序数组,@Benchmark 标出待测方法;Scope.Thread 表示每个基准线程持有自己的状态。方法返回搜索结果,以便框架消费结果。这里始终查找末尾元素,只覆盖一种查询位置,不能代表所有命中、未命中或真实业务查询分布。
报告至少记录 CPU、操作系统、JDK 版本与 JVM 参数、输入分布、测量模式、分配率和 GC,还要说明以下设置:
warmup:预热,让代码在正式测量前执行,降低即时编译等启动过程的影响;measurement:正式测量的轮次和每轮时长,用于观察重复测量的结果与波动;fork:独立 JVM 进程的运行次数,减少同一进程中已有运行状态的影响。
常见错误包括仅用一次 System.nanoTime() 计时、不消费结果,以及比较算法本身时把数据准备也算进去。结果无人使用时,编译器可能消除待测工作;若生产每次请求都需要准备数据,则又应单独测量包含准备成本的完整流程,关键是先定义测量边界。
接口还包含网络、排队、序列化和外部依赖等成本,因此不能用微基准结果直接承诺 SLA(服务等级协议中约定的延迟、可用性等目标)。JMH 用于比较局部实现,端到端容量仍要通过压测和生产指标验证。
10. 从测试进入生产证据
测试输入无法覆盖生产中的全部规模和分布。上线后,应同时记录输入特征和资源成本,才能判断变慢是因为数据变大、分布改变,还是运行环境变化。下面按风险列出可收集的证据。
| 风险 | 建议证据 |
|---|---|
| 输入放大 | 输入规模直方图、拒绝或分片次数 |
| 算法退化 | 执行耗时分位数、比较或迭代次数 |
| 内存换时间 | 分配率、堆占用、GC 暂停 |
| 递归过深 | 最大深度、StackOverflowError |
| 队列或堆膨胀 | 当前大小、峰值、丢弃数量 |
| Hash 或分片倾斜 | 桶分布、节点负载标准差、热 Key |
| 近似结构失准 | 实际元素数、填充率、抽样误判率 |
输入规模直方图记录各规模区间出现的频次,耗时分位数显示某个比例的请求在多长时间内完成,分配率反映单位时间创建对象所占的内存量。桶是哈希值映射到的存储位置;节点负载标准差描述负载的离散程度;热 Key 是访问特别集中的键。近似结构用较低成本换取一定误差,填充率和抽样误判率有助于观察这种误差是否仍在业务可接受范围内。
排障时先确认输入与分布是否变化,再检查实现版本和资源环境。一次 CPU 飙高本身无法区分这些原因,需要把同一时段的输入、耗时、迭代次数与资源指标结合起来判断。
11. 一套可复用的验证清单
- 输入、输出、副作用和非法输入是否定义?
- 正确性依赖哪些不变量或前提?
- 是否存在可用于小输入的暴力基线?
- 是否覆盖空值、重复、极值、溢出和退化结构?
- 随机测试失败能否用 seed 重放?
- 多解问题验证的是性质还是碰巧相同的输出?
- 复杂度是否把内部 API、输出成本和预处理算进去?
- 基准是否固定 JDK、数据分布和测量模式?
- 性能收益是否以额外内存、稳定性或精确性为代价?
- 上线后有什么指标能证明算法正在退化?
12. 总结
算法质量由正确性证明、自动化验证和真实负载证据共同构成。
- 契约和不变量解释算法为什么正确。
- 暴力基线、差分测试和性质测试负责发现实现偏差。
- 复杂度分析、JMH 与端到端指标分别回答增长趋势、局部成本和生产容量问题。