随机测试终于报错，却给了我一长串数：怎样把反例缩到一个元素？

随机测试终于报错却给了我一长串数怎样把反例缩到一个元素前面的判题器文章主要在问测试能不能真的找出错误。这次接着往后走。假设它已经找到一组失败数据接下来怎么读它如果输入里有几十个数我们很容易一会儿盯住前面一会儿又怀疑后面。可以先做件更笨、也更有用的事删掉其中一部分再运行一次。删完仍然错说明那部分至少不是这次复现所必需的。这个判断能不能交给程序反复做先拿一组能手算的题试试。先约定“错”到底是什么题目是给定非空整数数组求非空连续子数组的最大和。例如[-3,-1,-2]的答案是-1不能什么也不取而返回0。我们故意放进一个边界有问题的实现作为被测程序。它的错误不是本文要优化的算法而是缩减器要追踪的对象def candidate(a): best current 0 for x in a: current max(0, current x) best max(best, current) return best参考程序则把所有非空区间枚举出来直接求和def reference(a): return max((sum(a[i:j]) for i in range(len(a)) for j in range(i 1, len(a) 1)), defaultNone)它写得慢每次求和还要扫区间总体是O(n³)但这里输入短优先要的是简单、独立、好检查。不能再写一个结构相同的优化算法结果两个程序共享同一处错误。然后给输入分三种结果def outcome(a): if not a: return INVALID return FAIL if candidate(a) ! reference(a) else PASSFAIL才说明原问题仍能复现。空数组违反题面是INVALID不能因为它触发了异常就把它当成“更好的反例”。拿真实跑出的那组数先删一半固定随机种子1103每组生成12个[-9,9]整数。本次第4452组才出现输出不一致[-3,-3,-8,-4,-4,-8, -1,-9,-5,-4,-6,-7] 参考答案-1 被测输出 0这次不是手工挑出一个漂亮输入再说它是随机生成的固定种子和生成循环都在文末。种子用来重现本次Python运行不保证所有语言的随机数生成器产生同一串数。删去前六个留下后六个。重新对拍仍然不一致原来 [前六个] [后六个] 操作 删掉 留下 [-1,-9,-5,-4,-6,-7] 参考-1被测0仍然FAIL那就接受这次删除。下一轮对剩下的六个数继续做12个数 | 删前6个仍错 v [-1,-9,-5,-4,-6,-7] | 删前3个仍错 v [-4,-6,-7] | 删前1个仍错 v [-6,-7] | 删前1个仍错 v [-7]到这里参考答案是-7被测输出还是0。只盯这个输入就容易找到问题了best从0开始current又始终不小于0全负数就永远抬不起答案。但题目要求至少选一个元素。修复这个具体算法可以从首元素初始化而不是让空区间参与竞争def corrected(a): current best a[0] for x in a[1:]: current max(x, current x) best max(best, current) return best缩减的作用不是替我们证明修复正确而是把问题缩到不容易看岔的地方。修复以后还得回归原始失败输入以及其他边界。如果删一半以后不再错了呢刚才每轮都恰好能删掉第一块这是该用例的结果不能写成通用规则。假设当前分成左右两块删左边以后通过了就把左边放回去再试删右边。两边单独删除都不能保留错误也不代表结束了。可以把当前输入划成四块一次只删一块试试。当前 [甲][乙][丙][丁] 试1 [乙][丙][丁] PASS - 不接受恢复 试2 [甲] [丙][丁] FAIL - 接受继续缩每次都拿当前仍失败的输入当起点保留元素顺序只删除一个连续块。接受以后重新分块一轮都删不掉就把块分得更细最后细到单个元素。这和delta debugging的分块缩减思想相关。本文实现只尝试“去掉一块后剩下的部分”是一个便于读懂的删除缩减器没有把它冒称为完整复刻的标准ddmin。原作者的实现与接口可以对照Andreas Zeller的Delta Debugging代码。核心函数如下test需要给出稳定的PASS、FAIL或INVALIDdef reduce_failure(values, testoutcome): current list(values) if test(current) ! FAIL: raise ValueError(input must reproduce the failure) calls 1 history [] granularity 2 while len(current) 2: parts min(granularity, len(current)) changed False for i in range(parts): lo i * len(current) // parts hi (i 1) * len(current) // parts trial current[:lo] current[hi:] result test(trial) calls 1 history.append({before: current[:], removed: [lo, hi], trial: trial, outcome: result, accepted: result FAIL}) if result FAIL: current trial granularity max(2, parts - 1) changed True break if changed: continue if parts len(current): break granularity min(len(current), parts * 2) return current, history, calls这里最值得盯住的是if result FAIL只有这一种结果可以替换current。其他结果只是说明这次删除不合适。输入长度作为一个一直下降的量防止接受操作来回打转。没有接受删除时块数会增加最多试到每块一个元素不会永远增加下去。最坏情况下单是调用test的次数就可能达到O(n²)量级。每次复制列表和运行被测程序还另有成本不能因为缩减结果很短就叫它线性算法。本例参考程序本身很慢所以我们只对小输入做这套验证。“一个也删不掉”就是最短了吗对[-7]再删就只剩空数组不满足题目它已经不能继续删除。不过不能把所有用例都概括成“缩减器能得到全局最小反例”。看一个专门展示限制的判定规则只有[1,2,3,4]、[3,4]、[1]返回FAIL其余非空输入都PASS。起点[1,2,3,4]FAIL 删前半 - [3,4]FAIL接受 再删3 - [4]PASS 再删4 - [3]PASS 所以停在[3,4] 可是[1]也FAIL而且更短。我们走到了一条保留错误的删除路径走到后来不能单独删除任何元素。这叫相对于当前删除操作的1-minimal删掉任意一个元素都无法保持有效失败。它不承诺所有删除路径里长度最短也没有把数值大小优化到最简单。失败可能依赖元素之间的组合不具有“多删一点一定更容易通过”这样的单调性。早期选择了哪条分支会影响最后留下的反例。把它接到自己的判题器要改哪里先改test不要急着改缩减策略。数组题可以返回两份答案是否不一致图题删边时还要检查点编号和连通性等题面要求操作序列删掉“创建对象”以后后面操作可能不合法。如果要追踪某类崩溃应检查退出码、错误种类或相应特征。不能原本想研究错误答案缩着缩着却变成“进程起不来”仍然一概当成同一个FAIL。超时也需要独立判定和稳定重跑不能把临时机器负载当成确定性失败。原始输入也要保留。缩小后的输入方便定位原始输入则用来确认修复没有只照顾这个小例子。附完整程序与验证方式下面保存为shrink.pyPython3直接运行不需要安装第三方库。python3 shrink.py程序保存随机起点、每次试删的下标范围、判定结果和最终反例。它还枚举长度1到6、取值来自[-2,-1,0,1,2]的全部19530个非空数组先检查修复版与暴力答案一致再对其中126个失败输入检查缩减后仍错、顺序未改、每个接受步骤仍错、单删任意一个元素都不能保持失败。另外有无效输入约束和上面的“1-minimal不等于最短”对照。这里验证的是明确的性质单看程序最后打印passed并不知道它有没有把一个已经通过的输入也接受下来。A deterministic wrong implementation and a deletion-only failing-input reducer. import itertools import json from pathlib import Path import random def reference(a): return max((sum(a[i:j]) for i in range(len(a)) for j in range(i 1, len(a) 1)), defaultNone) def candidate(a): best current 0 for x in a: current max(0, current x) best max(best, current) return best def outcome(a): if not a: return INVALID return FAIL if candidate(a) ! reference(a) else PASS def corrected(a): current best a[0] for x in a[1:]: current max(x, current x) best max(best, current) return best def reduce_failure(values, testoutcome): current list(values) if test(current) ! FAIL: raise ValueError(input must reproduce the failure) calls 1 history [] granularity 2 while len(current) 2: parts min(granularity, len(current)) changed False for i in range(parts): lo i * len(current) // parts hi (i 1) * len(current) // parts trial current[:lo] current[hi:] result test(trial) calls 1 history.append({before: current[:], removed: [lo, hi], trial: trial, outcome: result, accepted: result FAIL}) if result FAIL: current trial granularity max(2, parts - 1) changed True break if changed: continue if parts len(current): break granularity min(len(current), parts * 2) return current, history, calls def check_reduction(original, testoutcome): reduced, history, calls reduce_failure(original, test) assert test(reduced) FAIL # A subsequence, not a reordered or fabricated input. it iter(original) assert all(any(x y for y in it) for x in reduced) assert all(test(reduced[:i] reduced[i 1:]) ! FAIL for i in range(len(reduced))) for step in history: lo, hi step[removed] assert step[trial] step[before][:lo] step[before][hi:] if step[accepted]: assert test(step[trial]) FAIL assert len(step[trial]) len(step[before]) return reduced, history, calls def main(): rng random.Random(1103) attempts 0 while True: attempts 1 original [rng.randint(-9, 9) for _ in range(12)] if outcome(original) FAIL: break if attempts 100000: raise RuntimeError(no reproducible failing input) reduced, history, calls check_reduction(original) failures 0 tested 0 for n in range(1, 7): for values in itertools.product([-2, -1, 0, 1, 2], repeatn): tested 1 assert corrected(values) reference(values) if outcome(values) FAIL: check_reduction(list(values)) failures 1 # A deterministic non-monotonic predicate forces a local minimum. def local_trap(a): return FAIL if a in ([1, 2, 3, 4], [3, 4], [1]) else (INVALID if not a else PASS) trap, trap_history, _ check_reduction([1, 2, 3, 4], local_trap) assert trap [3, 4] and local_trap([1]) FAIL try: reduce_failure([1, 2]) except ValueError: pass else: raise AssertionError(a passing input must be rejected) invalid_trials [] def constrained(a): result FAIL if len(a) 2 else INVALID invalid_trials.append((a[:], result)) return result constrained_result, _, _ check_reduction([7, 8, 9], constrained) assert len(constrained_result) 2 assert any(r INVALID for _, r in invalid_trials) # Reject reducers that lose failure, change order, or accept invalid emptiness. mutants {return_empty: [], return_original: original[:], accept_passing: [1, 2]} rejected {} for name, values in mutants.items(): valid_failure outcome(values) FAIL one_minimal valid_failure and all(outcome(values[:i] values[i 1:]) ! FAIL for i in range(len(values))) rejected[name] not one_minimal assert all(rejected.values()) assert corrected(original) reference(original) record {passed: True, seed: 1103, attempts: attempts, original: original, expected: reference(original), actual: candidate(original), reduced: reduced, reducedExpected: reference(reduced), reducedActual: candidate(reduced), calls: calls, history: history, exhaustiveInputs: tested, failingInputsReduced: failures, correctedMatchesOracle: True, badOutputControlsRejected: rejected, oneMinimalNotGlobal: {input: [1, 2, 3, 4], reduced: trap, smallerFailure: [1], history: trap_history}, constrainedResult: constrained_result} out Path(__file__).with_name(results.json) out.write_text(json.dumps(record, indent2)) print(json.dumps({k: v for k, v in record.items() if k not in (history, oneMinimalNotGlobal)})) if __name__ __main__: main()