# 0029 · 常数因子优化：先量再动（参考解）

这一课回答一个问题：**同一道题、同一个答案，为什么有的写法快两个数量级？**

答案不在「写得更漂亮」，在**每一段各执行多少次操作**。所以这一课是一条先量后改的链：

    （1）分段计时 ──▶ 瓶颈在哪一段      ← 不能看代码形状，要看操作次数
    （2）上三到四招 ──▶ 每上一招回验答案  ← 换容器 → 整体读入 → 提前算不变式 → 用内置
    （3）和内置比 ──▶ 差在哪一层         ← 循环那一层？查找那一层？还是复杂度？
    （4）故意写错一次 ──▶ 对拍抓得住吗    ← 抓不到错的对拍器，每轮都说「没事」

四个任务就是这条链的四段：

| 任务 | 文件 | 要交的东西 | 这一段在链上的位置 |
| --- | --- | --- | --- |
| 1 · 分段计时 | `task1_bottleneck.py` | `segment_ops` / `analyze_segments` / `count_size_calls` | 先量出瓶颈：三段各多少次操作 |
| 2 · 依次上招 | `task2_tuning.py` | `optimization_steps` / `tier_steps` / `solve_tier` / `tier_times` | 四招各改掉了什么，每招都留记录 |
| 3 · 和内置比 | `task3_builtin.py` | `compare_with_builtin` / `work_of` / `recursion_ceiling` | 倍率好看不够，要说清差在哪一层 |
| 4 · 故意写错 | `task4_break_it.py` | `audit_broken_once` / `count_matches` / `audit_after_fix` | 对拍器自己也要被验一次 |

把这一份里的文件拷进你的任务目录就能直接跑（`tools.py` 与 `run_tests.py` 两侧内容完全相同）：

    py run_tests.py        # 在 lab/solutions/0029-constant-factor-tuning/ 目录里直接跑

这一课真正要拿走的三句话：

1. **不测就猜瓶颈在哪。** 看着最重的三段（建集合、排序、若干次 `in`），实测最慢的
   往往是那个「只有几百次循环」的——因为它每次循环里都在做一件贵的事。
2. **能数就不要计时。** 秒数会被机器、调度、别的进程带着走；「这一段执行了多少次操作」
   换台机器还是同一个整数，而且**能被另算一遍**。这一课判死人的全是次数。
3. **优化不许改答案。** 顺序永远是：先让它对 → 再让它快 → 每快一次都重新证明它对。
   第 4 段的那个故意写错，就是把这句话反过来验一次。

## 逐题：为什么这么写

### 任务 1 · 瓶颈在三段里的哪一段

三段跑同一批数据（20 万元素、350 个键）：

| 段 | 做什么 | 看着像多重 | 操作次数 | 实测（课件） |
| --- | --- | --- | --- | --- |
| A_set | 把一个元素装进集合 | 最重 | `size` = 200000 | 0.0020 秒 |
| B_sort | 排序这同一批元素 | 也重 | `size * log2(size)` ≈ 350 万 | 0.0006 秒 |
| C_in | 若干次「这个键在不在数组里」 | 最无害 | `keys * size` = 7000 万 | 1.8992 秒 |

**C 段比 A 段贵 350 倍**（就是 `keys`），而它看着最轻：循环只有 350 次。
贵在**每次循环里都在扫一整条 20 万元的数组**——列表的 `in` 是线性扫描。

课件里那两格对照（2000 次 `in`，两边都找到 351 个）：

    列表  1.8992 秒
    集合  0.0021 秒          → 230 倍，答案一样

`count_size_calls` 那一格是「条件里的重复求值」：

    while i < cnt.size():     ← 每次都问一遍，循环体跑 n 次，条件判 n + 1 次 → 1001
    limit = cnt.size()        ← 只在外面问一次                              → 1
    while i < limit:

**是 n + 1 不是 n**：退出循环前还有一次失败的比较。课件量出来的就是 1001 与 1，
两版答案都是 499500。判分换成 n = 1234 再问一遍（1235 与 1），写死 1001 会露。

`analyze_segments` 那一格要小心：判分给两次**不一样的**实测值
（一次只有 C_in 是 0.25 秒、一次只有 A_set 是 0.25 秒），`slower_true` 必须跟着
**传进来的值**走，不能写死某一段——这一课的第一句话就是「别凭形状猜」。

### 任务 2 · 四招：每一招改掉了哪一格

判分把「操作次数」拆成四格确定量：**循环次数 / 相等比较次数 / 读入次数 / 建集合次数**。
四招各改掉其中一到两格：

| 级 | 这一招 | 循环 | 相等比较 | 读入 | 建集合 |
| --- | --- | --- | --- | --- | --- |
| 0 | 起点：列表 `in` + 逐行读入 | `keys * size` | `keys * size` | `size` | 1 |
| 1 | 换容器：列表 `in` → 集合 `in` | `keys` | `keys * size` | `size` | 1 |
| 2 | 整体读入：逐行 → 一次 `read().split()` | `keys` | `keys * size` | 1 | `keys` |
| 3 | 提前算不变式：集合提到循环外 | `keys` | `keys` | 1 | 1 |
| 4 | 用内置：手写循环 → `sum` + generator | 1 | `keys` | 1 | 1 |

判分自己的规模（9000 个值 / 120 个键）上就是这一串：

    (1080000, 1080000, 9000) → (120, 1080000, 9000) → (120, 1080000, 1)
    → (120, 120, 1) → (1, 120, 1)

注意第 2 招那一格：**读入从 9000 降到 1，但建集合从 1 涨到 120**——
逐行读的时候数组是边读边攒的，整体读入之后每一轮都得自己重建一次集合。
这就是第 3 招（提前算不变式）要收拾的东西。四招的顺序不是随便排的：
换容器省的是**复杂度**，抠语法省的是**常数**，先把钱大的做掉。
课件里 `int(input())` 逐行 10⁶ 行是 0.4216 秒、`read().split()` 是 0.0534 秒（7.9 倍），
但那是第二招，排在换容器后面。

读入那一格**必须由读入器自己记出来**：第 2 级起走一次 `reader.read_all()`，
第 0、1 级走逐行读（每行一次 `reader.next_number()`）。
判分不只比那四个数，还会自己再数一遍读入器的账（`read_all` 1 次 / 逐行 0 次）。

`tier_times` 在这两处用到耗时，两处都带保护：

- **退化守卫**：四级全是 `0.000000` 就 FAIL（留白版就栽在这一条）；
- **噪声容差 0.75**：换容器那一处只要求落在基线的 0.75 倍以内，不核具体倍数。

真正判死的是那四行次数。另有一条**不靠时钟的因果证据**：第 4 级跑 16 遍只让读入器
被调 0 次，第 0 级跑 1 遍就要 400 次——优化掉的是操作次数，这一条不会被机器快慢影响。

### 任务 3 · 倍率好看不够，要说清差在哪一层

五栏，每栏交回「两边答案 / 两边各多少次值访问 / 差在哪一层」：

| 栏 | 手写版值访问 | 内置版值访问 | 差在哪一层 | 课件倍率 |
| --- | --- | --- | --- | --- |
| contain | 120000000（`keys * arr`） | 130 | **查找**：线性扫描 O(n) 对平均 O(1) | 230 倍 |
| sort | 3123750（`n(n-1)/2`） | 2500 | **复杂度**：O(n²) 对 O(n log n)，常数只占一小部分 | 1134 倍（n = 3000） |
| sum | 300000 | 300000 | **循环**：手写每轮 FOR_ITER + 加法 + STORE_FAST，`sum` 在 C 里跑 | 4.8 倍 |
| min | 500000（每轮扫全表） | 100000 | **每轮代价**：反复 `min` 对 `nsmallest` 的堆 | — |
| role | 480000（平均比 8 次） | 60000 | **分支**：if/elif 一路比下来，查表只索引一次 | 1.06× / 2.65× / 4.26× |

`sum` 那一栏两边值访问次数**一样**（都是 n）——差的是谁在绕这个循环。
所以「次数一样、快 4.8 倍」不矛盾，它正好说明这一栏差的是**循环那一层**。
反过来 `sort` 那一栏的倍率上千，绝大部分是复杂度，把它当成「内置快一千倍」
就学错了东西——课件那句「查表反而慢 12%」也是同一个坑：**两个版本必须严格可比**，
不然量出来的倍率没有意义。

`recursion_ceiling` / `recursion_probe` 这一格刻意**不核那个具体的数**：
默认上限 1000，主模块本身占一层，你在第几层调用还差几层——
判分自己量是 994，参考解在自己那个位置量是 992，差 2 层**不算错**。
核的是机制：**有个 n 撑得住、再往上就不行**。课件那组数是
n = 900 时迭代比递归快 6.7 倍、n = 999 时那条递归路径 RecursionError。

### 任务 4 · 对拍器自己也要被验一次

故意把 `while i < stop` 里的 `stop = n` 写成 `stop = n - 1`——最后一个元素不看了：

    差别只有一处：stop = n - 1 if broken else n

50 组固定数据（种子钉死）上的结果：

    对的那版加起来 586
    坏的那版加起来 554        ← 差的正是每组少看的那个元素
    坏版露了几组   32        ← 50 组里 32 组被抓到

为什么不是 50 组？因为有些组里最后一个元素本来就不在 `[lo, hi]` 里，
两版答案一样。空数组那一组更是两版都交回 0——**这些「一样」不算对拍失效**，
它们只是没有反例。

**证据那一格才是重点**：最早对不上的那组原始数据（`[2, 6, 3, 4, 3, 5, 6, 6, 3, 0, 0, 6, 6, 3, 4, 5, …]`）
连同两版各自的答案一起交回。有反例的否掉比没有反例的通过更有价值。
单元素数组 `[2]` 上是对的那版 1、坏的那版 0——**错得不多，但已经错了**，
这正是它值得当例子的原因：改一处都要回验，靠看是看不住的。

最后 `audit_after_fix` 必须是 0 组不一致：**坏版能被我抓到、改回来之后就抓不到了**，
两头都对上，才说明「抓到的」真的是我写坏的那一处，而不是碰巧。

## 常见错法（判分逐条盯着）

| 错法 | 症状 | 判分读的那一条 |
| --- | --- | --- |
| 凭代码形状猜瓶颈（写死 `'A_set'`） | 判分给两次不同的实测值，第二次就露 | `slower_true 不是传进来的实测值里最慢的那一段` |
| `size()` 次数写成 n（忘了那次失败比较） | 1000 对 1001 | `n = 1000 时 size() 被调了 1001 次…` |
| 三段操作次数写死 | 判分换两组规模复算 | 三组规模各一条 PASS/FAIL |
| 对拍时把列表版答案改成集合版的 | 「优化不许改答案」破了 | `两个容器给出同一个答案` |
| 四级计数写死、或不算建集合那一格 | 第 2 级的「建集合 120 次」对不上 | `四级的前三格计数…逐级一致` |
| 读入次数按公式写、不真调读入器 | 判分自己再数一遍读入器的账 | `第 N 级的读入器账目对得上` |
| `tier_times` 交回占位值 0.0 | 四级全 0.000000 | `四级耗时全是 0.000000——这是**占位值**` |
| 用单次计时（不看中位数） | 第 0 级抖动把 3.0 倍量成 1.0 倍 | 换容器那一处的噪声容差 |
| 把 `sort` 的倍率当成「常数因子」 | 学错了层 | `sort 栏「差在哪一层」点到了 复杂度` |
| 手写版与内置版数据不是同一份 | 倍率没有意义 | `两边答案一致（…）` 那一条 |
| 递归边界写死 998 | 换个调用位置就露 | `递归的边界…判分核的是这个机制` |
| 对拍只报「抓到几组」不交证据 | 反例无从复现 | `证据那一格是**最早对不上的那组数据**本身` |
| 坏版一组都没抓到还判「过」 | 对拍器永远说没事 | `坏的那一版在 32 组上露了` |
| 改函数名 / 改判分要读的 `print` 行 | 判分「没看到某一行」 | 行数那三条 `打印了 N 行` |
| 源码里手写连续三个反引号 | 打断阅卷工具链 | 判分扫源码那一条 |

## 判分在读什么

`run_tests.py` 分五层（+ 探针五条副线），缺一不可：

| 层 | 验什么 | 关键证据 |
| --- | --- | --- |
| 1 | 三段操作次数（**三组规模**）、`slower_true` 跟着实测值走、`size()` 是 n + 1、两个容器同一个答案 | `tools.segment_ops_canonical` 现算 |
| 2 | 四级四格计数**逐级**对照、读入器账目、四级答案一致、退化守卫与噪声容差 | `canonical_trace_table` 现算 + `ReadCounter` 的账 |
| 3 | 五栏答案两边一致、值访问次数按规模算、`layer_of` 点到关键词、递归边界是机制 | `expect_answer` / `expect_times` 现算，不核死 998 |
| 4 | 对拍在 5 组数据上（含空数组、单元素）逐格对、坏版必须被抓到并带出证据、改回来 0 组 | `audit_run` / `count_matches` 现算 |
| 5 | 四个脚本单跑退出码 0、0 处 Traceback、**打印行数与参考解逐行一致**、耗时不是占位值 | 行数 26 / 34 / 40 / 22 |

两路证据缺一不可：

1. **跑任务脚本、读它自己打印的行**（主要证据）。判分按标签找行，
   行里的值都是从函数交回的东西里查出来的。
2. **另起探针 `import` 学生的函数，用判分自己造的数据试**（独立证据）。
   探针用的是判分自己的种子与规模（`PROBE_SEED = 2718281`、规模 9000 / 120 / n = 1234），
   期望值全部由 `tools` 里的另一套实现现算——**只写 print 不写实现拿不到 PASS**。

判分里核对的是那些**确定量**：三组规模的操作次数、`1001 / 1` 与 `1235 / 1`、
`143 / 177 / 72`、四级四格计数、读入账目、五栏答案与值访问次数、`586 / 554 / 32` 组、
`0 组` 不一致。**耗时只在三个地方出现**，全部带保护：

- 任务 2 的四级耗时：退化守卫（全 0 就 FAIL）+ 换容器那一处的噪声容差 0.75；
- 任务 2 探针那一格：只要求「有一格不是 0」；
- 任务 1 / 任务 3 的耗时只打印，判分不拿它当判据。

留白版的成绩是 `0 层通过、5 层还没过（共 41 条 PASS、67 条 FAIL）`，
每一条 FAIL 后面都点名是哪个文件的哪个 TODO；参考解是
`5 层通过、0 层还没过（共 109 条 PASS、0 条 FAIL）`，连跑三次都是退出码 0。