从何时开始坏的 — 用六次把 64 个版本缩小
目标
编写能够区分好、坏和无法判断的机器判定器，用它分别对 64 个构建的历史和 4096 行输入数据对半切分，找到边界。再加上绕开无法判断的路径和对边界做全量验证的路径，并同时记录如果用顺序查找会是多少次。
为什么重要
“上周之前还是好的”和“只有昨天的文件会崩”是同一种形态的问题：有一条边界，前后泾渭分明。从头逐个查看，分别是 64 次和 4096 次，而对半切分，只要六次和十二次。 造成这种差别的不是工具，而是判定器。如果掺入人看着屏幕判断的环节，就没法重复十次，大概到第五次，就会忘了自己说过哪一边是好的。 难的不是对半切分的代码，而是边界条件。把无法启动的构建算作坏，元凶就会向前推移；从片段中去掉表头，所有片段都会失败并指向第 1 行；在中途修好后又坏掉的历史中，答案本身就是错的。 评分器不会相信你写的文字。它会把自己生成的历史和数据摆在临时目录中，实际运行你的工具，同时测量边界是否正确，以及用了多少次才找到。边界每次运行都在不同的位置，所以无法把数值背下来填进去。
步骤
- 创建并运行 /root/bisect/gen_history.py，生成 64 个构建的历史，以及 /root/bisect/ref.csv、/root/bisect/rows.csv、/root/bisect/loader.py。
- 创建 /root/bisect/judge.py，让它把一个构建判定为 good、bad、unknown 之一。退出码分别为 0、1、125。
- 用 /root/bisect/bisect_run.py 把历史对半切分，找出第一个变坏的构建，并保存到 /root/bisect/bisect_result.json。63 个候选，六次就能完成。
- 让 bisect_run.py 在遇到无法判断的构建时，改为向相邻的构建绕开重新询问，并让它在整个区间都无法判断时不指认某一个构建。
- 用 /root/bisect/row_bisect.py 找出让加载器崩溃的行，并保存到 /root/bisect/row_result.json。片段中必须始终带上表头。
- 在 /root/bisect/probe_count.json 中并排写下顺序查找和二分查找的最坏次数，以及实际用掉的次数。
- 用 /root/bisect/verify_bisect.py 对边界做全量验证，生成 /root/bisect/verify_result.json。遇到非单调的历史时，必须把反例按名称写出来。
- 用 /root/bisect/summary.json 和 /root/bisect/bisect_report.md 分四节进行报告。
参考
- 判定约定：
python3 /root/bisect/judge.py --rev <판 디렉터리> --input <csv> --expect <정수>（占位符依次为构建目录、CSV 文件、整数）向标准输出打印 good、bad、unknown 中的一个词，并以退出码 0、1、125 结束。 - 流水线约定：
python3 <판>/pipeline.py --in <csv>（占位符依次为构建、CSV 文件）输出一行total=<정수>（占位符为整数）并以 0 结束。无法启动的构建以非 0 的退出码结束。 - 查找约定：
python3 /root/bisect/bisect_run.py --hist <이력 디렉터리> --input <csv> --expect <정수> --out <json>（占位符依次为历史目录、CSV 文件、整数、JSON 文件）输出一个包含 first_bad、last_good、probe_count、probes、undecided 的 JSON。构建名称就是目录名称（例如 r41）。 - 行查找约定：
python3 /root/bisect/row_bisect.py --csv <파일> --loader <적재기> --out <json>（占位符依次为文件、加载器、JSON 文件）输出 bad_row（不含表头、从 1 开始计数的行号）、probe_count、rows。加载器用python3 <적재기> <csv>（占位符为加载器）来调用，退出码不为 0，说明元凶在这个片段中。 - 验证约定：
python3 /root/bisect/verify_bisect.py --hist <디렉터리> --input <csv> --expect <정수> --boundary <판 이름> --out <json>（占位符依次为目录、CSV 文件、整数、构建名称、JSON 文件）输出 boundary_bad、prev_good、monotone、contradictions、checked。 - 次数计算：对于 n 个候选，顺序查找的最坏情况是 n 次，二分查找的最坏情况是向上取整的 log2(n) 次。历史的候选数是构建数减一（因为从第一个构建被视为好的开始），数据的候选数是行数。
- 常见错误：把无法判断折算成坏，从片段中去掉表头，找到边界后不验证，在做出判定器之前就用眼睛去查找。
- 本实验的假设：用退出码 125 表示无法判断，是原样借用了 git bisect run 的约定，并不是标准规定的值。
- 不要编写负载测试。每次评分的预算是 60 秒，Pod 为 2 核。
拿到构建历史和新的输入
创建并运行 /root/bisect/gen_history.py，生成 64 个构建的历史（从 /root/bisect/hist/r00 到 r63），以及 /root/bisect/ref.csv（300 行）、/root/bisect/rows.csv（4096 行）、/root/bisect/loader.py。
在现场拿到手的不是代码，而是数据。把这个脚本原样保存并运行即可。最后一行输出的 expect 值（ref.csv 的正确合计）在后面的步骤中会一直用到，请记下来。
让机器来判定好与坏
创建 /root/bisect/judge.py，让它把一个构建判定为 good、bad、unknown 中的一个词。退出码分别为 0、1、125，无法启动的构建不是坏，而是无法判断。
判定器是一个程序：它实际运行该构建的 pipeline.py，把 total 值与预期值进行比较。要把三种结果分清楚——能运行且值正确是 good，能运行但值不同是 bad，根本运行不了或找不到 total 就是 unknown。125 是 git bisect run 读作“跳过”的值。
把历史对半切分，找出边界
用 /root/bisect/bisect_run.py 找出第一个变坏的构建，并把结果保存到 /root/bisect/bisect_result.json。其中必须包含 first_bad、last_good、probe_count、probes、undecided；如果对 63 个候选询问超过 60 次，那就不是二分查找。
设定已知好的位置 lo 和已知坏的位置 hi，不断询问中间位置并拉近其中一端，直到两者之间只剩一格。要先确认两端，才能知道前提是否成立。把询问过的构建名称按顺序收集起来，probes 和 probe_count 自然就有了。
绕开无法启动的构建
让 bisect_run.py 在遇到无法判断的构建时，向相邻的构建一格一格地挪动并重新询问，并把绕开的构建名称收集到 undecided 中。如果整个区间都无法判断，就不要指认某一个构建，而要用 last_good 和 first_bad 报告剩余的区间。
如果把无法判断折算成坏，边界就会向前推移，无辜的构建就会成为元凶。如果中间的构建无法判断，就放弃这个位置，像 mid-1、mid+1、mid-2 这样向左右一格一格地扩大范围，找到能够判断的相邻构建。如果区间内一个能够判断的构建都没有，那个区间就是答案——缩小范围同样是成果。
找出让加载器崩溃的行
用 /root/bisect/row_bisect.py 找出 /root/bisect/rows.csv 中究竟是哪一行让加载器停摆，并以 bad_row、probe_count、rows 的形式保存到 /root/bisect/row_result.json。bad_row 是不含表头、从 1 开始计数的行号。
原理与历史相同。制作只包含从头到第 m 行的片段交给加载器，如果失败，元凶就在其中。片段中必须始终带上表头——去掉的话，后半部分的片段会把第一行数据读成列名，导致所有片段都失败。4096 行的话，十二次就足够了。
统计用了多少次
在 /root/bisect/probe_count.json 中写入 history、rows、million 三项。每一项都包含 candidates、sequential_worst、bisect_worst，history 和 rows 还要包含实际用掉的次数 measured。million 的 candidates 是 1000000。
顺序查找的最坏情况就是候选数本身，二分查找的最坏情况是向上取整的 log2（候选数）。历史的候选数是构建数减一——因为从第一个构建被视为好的开始。measured 直接取前一步所保存 JSON 中的 probe_count。
全量确认边界是否真的是边界
用 /root/bisect/verify_bisect.py 对边界前后做全量检查，并把 boundary_bad、prev_good、monotone、contradictions、checked 保存到 /root/bisect/verify_result.json。如果边界之后有好的构建，或者边界之前有坏的构建，必须把它们的名称写入 contradictions。
查找是对数级的，验证是线性的。把所有构建各运行一遍，标出 good、bad、unknown，收集边界之后的 good 和边界之前的 bad，它们就是单调性被破坏的证据。无法判断不是反例——要单独统计。
用一页纸报告两条边界
在 /root/bisect/summary.json 中写入 revisions、first_bad、last_good、unknown、history_probes、rows、bad_row、row_probes、sequential_total、bisect_total，并在 /root/bisect/bisect_report.md 中分四节进行报告：## 무엇이 깨졌나、## 어떻게 좁혔나、## 몇 번 만에、## 남은 위험（韩文，依次意为“什么坏了”“如何缩小范围”“用了几次”“剩余风险”）。
sequential_total 是两个顺序最坏次数之和，bisect_total 是实际用掉的两个次数之和。报告中要写下第一个变坏的构建名称、元凶行号，以及这两个数字。客户买的不是结论，而是流程。