# 0030 · 压力测试与复盘（交卷之前你要检查什么）· 参考解 这一课把「样例过了就交」这件事拆成一条**能被程序检查**的链： ```text 一个可疑的实现 ──对拍（换一把尺子）──▶ 不一致的那几组 ──换数据范围（生成器）──▶ 同一句话的另一半 ──换运行姿势（多组数据）──▶ 第一组对、后面错 ──换数据规模（取模）──▶ 小数据上逐字相同 ──把上面四件事写进清单──▶ 交卷之前有据可查 ``` 四个任务就是这条链的四段： | 任务 | 文件 | 要交的东西 | 这一段在链上的位置 | | --- | --- | --- | --- | | 1 · 对拍 | `task1_brute_ref.py` | `run_trials` / `first_bad` | 候选解 × 三把尺子 | | 2 · 生成器的范围 | `task2_generator.py` | `run_pair` | 换一批数据再量一次 | | 3 · 多组数据要清空 | `task3_reset.py` | `class Solver` / `run_cases` | 换一种运行姿势 | | 4 · 取模 | `task4_modulo.py` | `first_diff` / `tail14` / `sample_rows` / `big_digits` / `random_bad` / `random_first` / `gap_cell` | 换数据规模 | 把这一份里的文件拷进你的任务目录就能直接跑（`tools.py` 与 `run_tests.py` 两侧内容完全相同）： ```text py run_tests.py # 在 lab/solutions/0030-stress-test-and-review/ 目录里直接跑 ``` 这一课真正要拿走的三句话： 1. **同一个思路的「参考解」是装饰品。** 它是照着候选解的想法另写一遍的，候选解错在哪儿 它就错在哪儿——所以它抓到 0 组不一致。**两把独立的尺子（暴力、分治）才是尺子**， 它们与候选解的想法毫无关系。 2. **抓不到 bug，先怀疑数据。** 同一个 bug、同一个对拍器、同样 300 组， 生成器多一句 `max(a) > 0`，成绩就从 33 组变成 0 组。**数据范围本身是实验的一部分。** 3. **小数据上看不出来的错，只有换规模才现形。** 忘了取模这件事在 n ≤ 30 上逐字相同 （n = 30 时两版都是 832040），一直到 **n = 45** 才分家。两条口径的差距是 2080 位。 ## 逐题：为什么这么写 ### 任务 1 · 对拍：为什么 0 / 58 / 58 / 0 这四个数一起看 ``` 种子 1，500 组随机数据（取值 -9..9，n 到 8）： → 与「同一个思路的参考解」对拍，不一致的: 0 组 → 与「独立暴力解」对拍，不一致的 : 58 组 → 与「独立分治解」对拍，不一致的 : 58 组 → 修好初值（best 从 -inf 起步）之后，与独立暴力对拍不一致的: 0 组 ``` 四个数各有各的用处，缺一个都读不出结论： | 那一格 | 数 | 它证明了什么 | | --- | --- | --- | | 候选解 × 同思路参考解 | **0 组** | 「同思路」这个说法是真的——两份代码错在同一个地方，所以一把尺子量不出差别 | | 候选解 × 独立暴力 | **58 组** | bug 真的存在，而且暴力这把尺子抓到了它 | | 候选解 × 独立分治 | **58 组** | 两把**互相独立**的尺子抓到的是同一批数据——58 不是某个实现的口味问题 | | 修好之后 × 独立暴力 | **0 组** | **对拍器本身是活的**：改掉 bug 之后它就安静了 | 最后一格是这一层的关键。「抓到 58 组」可以是好消息，也可以是坏消息——如果对拍器自己 在乱报（比如拿两个都错的实现互相比），那 58 组一文不值。**改好之后必须回到 0**， 这条 58 才作数。 58 这个数还有内容：它恰好是**全是负数**的那一类数据。候选解的 bug 是 ```python best = 0 # 错在这里：答案被按在 0 起步 for x in a: cur = max(0, cur + x) best = max(best, cur) ``` 题目只保证**子段非空**，所以 [-7] 的正确答案是 -7，而它交出 0。要让它露出来， 生成的数据里必须有「一组正数都没有」的那些组——这就是任务 2 的事。 第一个反例要连**组号**一起交： ``` 独立暴力抓到的第一个反例: 在第 23 组 数据 [-7] 候选解给 0 独立暴力给 -7 ``` 组号从 0 起，[-7] 排在第 24 位。`first_bad` 只能用 `cand_buggy(a) != ref_brute(a)` 判—— **拿同思路那把尺子找反例，永远找不到**（它们一致的时候是 500 组全一致）。 「修好初值」那一版不能只把 `best` 改成 `float('-inf')`： ```python best = cur = a[0] # 对：best 与 cur 都从头元素起步 for x in a[1:]: cur = x if cur < 0 else cur + x # 要么从这里重新开始，要么接着累 best = max(best, cur) ``` `cur = max(0, cur + x)` 那一句照样把当前段的和按回 0，模型还是「子段可以空」， 全负数据上仍然交出 0——**只改初值不改转移，等于没改**。空表要交回 `None` （`cand_fixed([])` 是 `None`，不是 0）：0 是一个合法的答案（比如 `[0]`）， 拿它当「没有答案」就分不清了。 ### 任务 2 · 生成器的范围：0 组 与 33 组是同一句话的两半 ``` 只造有正数的 300 组里抓到 bug 的有 0 组 允许全负的 300 组里抓到 bug 的有 33 组 ``` 同一个 bug、同一个对拍器、同样 300 组、同一个种子，**只换了生成器的范围**。 两行并排放在一起才是结论：「这个 bug 只藏在全负的数据里」。只报 33 组， 旁人会以为 bug 到处都有；只报 0 组，你会以为自己过关了。 `run_pair` 交回 `{'caught': …, 'groups': …, 'first': …}`，三个键都是判分接口： - `caught` 是**抓到 bug 的组数**； - `groups` 是**实际跑完的组数**——`until_bad=True` 时它会小于 `trials`； - `first` 是第一组反例的 `(组号, 数据, 候选解给的, 独立暴力给的)`，一个反例都没有时是 `None`。 `until_bad=True` 要在**抓到第一组时立刻停**（`groups == 1`），不许「跑到最后再回头找」。 种子在循环外抽一次、每组重抽 `n`：`rng.randint(1, n_hi)`——把种子放进循环里， 每一组都会退回同一个 n，成绩会跟着变。 ### 任务 3 · 多组数据：第一组往往是对的 ``` 三组数据 : [[1, 2, 3], [10, 20], [5]] 忘了清空 : [6, 36, 41] 每问都清空 : [6, 30, 5] 正确答案 : [6, 30, 5] 忘了清空对吗: False 每问清空对吗: True → 两组各自的第 1 组: 忘了清空 6 / 每问清空 6 / 期望 6 ``` 算一遍就明白 36 与 41 是怎么来的： ``` 第 1 组 [1, 2, 3] → 6 （两种跑法都是 6） 第 2 组 [10, 20] → 忘了清空：6 + 30 = 36 ；每问清空：30 第 3 组 [5] → 忘了清空：36 + 5 = 41 ；每问清空：5 ``` **第一组永远是对的。** 这就是为什么用样例试不出来：样例往往只有一组， 或者你只看了第一组的输出。多组数据的题，第一组的答案是最没有信息量的那一格。 `Solver` 的状态要真的放在**对象上**（`self.total`）： ```python class Solver: def __init__(self): self.total = 0 def reset(self): self.total = 0 def answer(self, a): for x in a: self.total += x return self.total ``` 两条不许做的事：`answer` 里**不许自己偷偷归零**（那样「忘了清空」这个 bug 就复现不出来， 这一节的整个现象都没了）；`run_cases` **不许把传进来的 `cases` 改掉**（交回新表）。 `run_cases` 的第三个参数 `solver` 是一道**缝**——判分往里面塞自己的 `Solver` 类， 数它被问了几次、被 `reset` 了几次。所以别写成 `def run_cases(cases, reset_per_case, solver=Solver())`：那样缝就堵上了， 判分塞进去的东西没人用。`reset_per_case=False` 时**一次 reset 都不许有**， 在循环外面补一次 `reset()` 也会在这里露。 ### 任务 4 · 取模：n = 45 这个分家点是算出来的 ``` MOD = 1,000,000,007 n 不取模（末 14 位） 取模后的值 两者相等吗 10 … 55 55 True 30 … 832040 832040 True 50 … 12586269025 586268941 False 100 …48179261915075 687995182 False 1000 …95166849228875 517691607 False 10000 …10059947366875 271496360 False → 第一个分家的 n（两版从这里开始不等）: 45 300 组随机 n（种子 3，n 在 21..120 之间）： 其中两版不相等的组数: 239 第一组不相等的 n: 51 不取模在 n = 10000 时的位数: 2090 位 取模后的值最多 10 位——两版差了 2080 位，在 n = 30 上却逐字相同 ``` 那张表是这一节的全部信息量，四格的顺序不能换：**n、不取模那个数的末 14 位、 取模后的值、两者相等吗**。最后一格要交**真正的布尔值**（`True` / `False`）， 不是 `1` / `0`、也不是字符串。 `45` 不是背下来的，是 `first_diff` 循环比出来的： ```python def first_diff(lo=1, hi=200): for n in range(lo, hi + 1): # 两端都要算进去 if fib_nomod(n) != fib_mod(n): return n return None # 这一段里一个都没有 → None，不是 0 ``` - `first_diff(41, 60)` 还是 45（把区间挪到分家点附近照样找得到）； - `first_diff(45, 60)` 还是 45（左端正好落在分家点上，`range` 要含 `lo`）； - `first_diff(1, 44)` 交回 `None`（n = 44 时两版还相等）。 `tail14` 是**从整个数上切尾巴**，不是先取模再切：n = 45 时两版已经分家， 但末几位还一样——这一格正是「局部相同、整体不同」。`x` 是 `None` 时要原样交回 `None`。 `big_digits(10000) = 2090`：不取模那一版是 2090 位，取模之后最多 10 位， 所以两条口径差了 **2080 位**。这两个数是「小数据看不出」的量化说法—— 在 n = 30 上，两条口径逐字相同；要到 n = 45 才分家；到 n = 10000 差了 2080 位。 **这一课一个耗时都不量。** 全部判据都是确定值（随机数一律固定种子： `T1_SEED=1` / `T2_SEED=2` / `RANDY_SEED=3`、`T4_FIRST_N=45`、`T4_BIG=10000`）。 ## 常见错法（判分逐条盯着） | 错法 | 症状 | 判分读的那一条 | | --- | --- | --- | | 只写 `print`、没真算 | 「不一致的」那一行是 `（还没接上）` | 每一层的探针都会另算一遍 | | 拿 `ref_same_idea` 找反例 | `first_bad` 永远找不到 | `first_bad() 交回的第一个反例对不上` | | `first_bad` 交回组号从 1 起 | 交回 24 | `组号是 24，期望 23` | | 「修好初值」只改 `best`、不改 `cur` | 修好之后还是 58 组 | 反向验证那一格要求 **0 组** | | `run_trials` 交回的表里少了某个键 | 那几格直接 FAIL | `run_trials() 交回的表里没有这一格` | | 组数交回 `'58'` / `58.0` / `None` | 类型不对 | `check_count` 要求是 `int` | | 生成器只造有正数的 | 成绩从 33 组变成 0 组 | `允许全负的 … 抓到 N 组，期望 33 组` | | 种子放在循环里 | 每组退回同一个 n | 判分拿**自己的生成器 + 另一个种子**再数一遍 | | `until_bad` 跑到最后才回头找 | `groups` 等于 `trials` | `until_bad=True 时「跑完几组」` | | `answer` 里自己把 `total` 归零 | 「忘了清空」复现不出来 | `没人调 reset 时第二组是 11` | | `reset` 没真的清零 | 每问清空那一版跟着错 | `调一次 reset 之后再问，交出 1` | | `run_cases` 把 `cases` 改掉了 | 交回的表与外层不一致 | `run_cases 把传进来的 cases 改掉了` | | `solver` 写成默认参数 | 判分塞不进去 | `被 reset 了 N 次` 那一格 | | `reset_per_case=False` 也调了 `reset` | 「忘了清空」那一版不叠了 | `被 reset 了 0 次` 是硬要求 | | `first_diff` 写死 45 | 换个区间就露 | `first_diff(41, 60)`、`first_diff(45, 60)` | | `first_diff` 用 `range(lo, hi)` | 右端漏掉一个 n | 区间两端都要算进去 | | `tail14` 从取模值上切 | n = 50 起末几位全是取模后的尾巴 | 探针逐点比 | | 第四格交回 `1` / `'True'` | 打印行对不上 | `第四格都是真的布尔值` | | `big_digits` 数取模后的位数 | 交回 10 左右，不是 2090 | `期望 2090 位` | | `random_bad` / `random_first` 写死参数 | 换种子就露 | `PROBE4_RANDY` 两组另算 | | 改函数名 / 改判分要读的 `print` 行 | 判分「没看到某一行」 | 所有「输出里没有…」的 FAIL | | 动了 `tools.py` | 58 / 33 / 2090 全对不上 | 逐字节比 SHA-256 | | 源码里手写连续三个反引号 | 打断阅卷工具链 | 全树扫一遍 | ## 判分在读什么 `run_tests.py` 分五层，缺一不可： | 层 | 验什么 | 关键证据 | | --- | --- | --- | | 1 | `0 / 58 / 58 / 0` 四个数、第一个反例第 23 组、探针 `[(7, 400), (13, 120)]` | 判分自己的 `probe_brute` / `probe_same_idea` / `probe_dc` / `probe_fixed` | | 2 | `0 组` 与 `33 组`、`run_pair` 在**判分自己的生成器**上另算、`until_bad` 早停 | `probe_runner` 现算，不吃 `tools` 里那两条口径 | | 3 | 换三组数据跑、两种跑法第一组相同、塞 `ProbeSolver` 数 reset 次数、`cases` 没被改 | `PROBE3_CASES = [[5, 5], [1], [2, 2]]`（第一组与第三组的答案刻意相等） | | 4 | 45 这个分家点、44/45/46 三个贴边点、末 14 位、2090 位、2080 位、两组随机参数 | 判分另选 `[1, 10, 44, 45, 46, 50, 30]` 那一组 n | | 5 | 四个脚本单跑退出码 0 且 0 处 Traceback、判分要读的行逐字、`tools.py` 逐字节相同、全树无连续三个反引号 | 同一批 n 把表**重拼一遍**逐字比 | 两路证据缺一不可： 1. **跑任务脚本、读它自己打印的行**（主要证据）。判分按标签找行（不按编号）， 行里的值都是**从函数交回的东西里查出来的**——留白版照样把这些行原样打出来， 只是值是占位的（`（还没接上）`）。 2. **另起探针 `import` 学生的函数，用判分自己造的数据试**（独立证据）。 探针的数据**刻意与脚本里那一批不同**：换种子（7 / 13 / 11 / 5 / 23 / 17 / 6）、 换规模（400 / 120 / 80 / 60 / 40 组）、换 n 的上限（6，不是 8）、 换三组用例（第一组的答案与后面某一组刻意相等）、换一组 n（44 / 45 / 46 贴着分家点）。 **只写 print 不写实现拿不到 PASS。** 判分里核对的是那些**确定量**：`0 / 58 / 58 / 0`、`第 23 组 [-7] 0 -7`、 `0 组 / 33 组`、`[6, 36, 41] / [6, 30, 5]`、`两组各自的第 1 组 6`、 `45 / 239 / 51 / 2090 / 2080`，以及**没有一条耗时断言**（本课一个时间都不量， 所以不会像 0026 那样出现 32/88 ↔ 31/89 的抖动）。 留白版的成绩是 `0 层通过、5 层还没过（共 22 条 PASS、57 条 FAIL）`， 参考解是 `5 层通过、0 层还没过（共 80 条 PASS、0 条 FAIL）`，连跑三次都是退出码 0、 三次输出逐字节相同。 留白版四个脚本单跑都是退出码 0、0 处 Traceback，打印行数与参考解**逐行相同**： ```text task1_brute_ref.py 16 行 task2_generator.py 17 行 task3_reset.py 7 行 task4_modulo.py 15 行 ``` `task4` 那张表是**固定 6 行**（一个 n 一行）的：还没接上时每一格打占位， 接上之后就是真值——**行数不许随进度变**，因为判分读的就是这几行。