用倍增实验找出并修复隐藏的二次复杂度

目标

通过把输入逐次翻倍的倍增实验，区分五个函数的增长率；修复最常见的隐藏二次复杂度（去重）并保持原有顺序；再用重复测量的分布证明改进，并外推目标规模下的耗时。

为什么重要

输入很小时，二次复杂度的函数也很快，所以测试能通过，只在生产环境里才变慢。只测一次的数字与一个噪声无法区分，只看代码样子做出的判断会漏掉只有一行的 in。因此要改变规模并反复测量，增长率用最小值之间的比值来表述，改进则用中位数和分布是否重叠来表述。评分器只用一个宽带来看时间本身，但会精确检查你写下的中位数、比值是否来自你自己的样本，以及改进后的函数是否给出与原函数相同的答案。

材料

位于 /opt/fixtures/svccs/measure/ 之下。只读取，不要修改。

suspects.py   함수 다섯 개(dedupe · newest_first · pack · flag_known · window_pairs)
              SUSPECTS[이름] → 함수, make_input(이름, n, seed=0) → 크기 n 의 입력(고정 시드)
params.json   sizes(함수마다 잴 네 크기, 두 배씩) · repeat_min(최소 반복 수 5)
              compare_sizes(7단계 크기) · target_n · budget_s(8단계 외삽 목표와 예산, 초)

导入方法：先执行 sys.path.insert(0, "/opt/fixtures/svccs/measure")，再执行 import suspects。

步骤

在 /root/svccs/measure/clock.json 中记录 perf_counter 和 time 两种时钟的性质。每个都是 {"monotonic", "adjustable", "resolution", "implementation"}，值原样取自 time.get_clock_info(이름)（占位符为时钟名称）。然后在 "choice" 中，用 "perf_counter" 或 "time" 写出用来测量区间的时钟。
在 /root/svccs/measure/bench.py 中编写 time_it(fn, make_input, n, repeat=7)。每次重复都用 data = make_input(n) 重新生成输入，并在此之后用 time.perf_counter() 测量 fn(data) 一次的耗时。返回 {"n", "repeat", "samples"(초 목록, 길이 repeat), "median"(statistics.median), "min"}（其中 samples 是以秒为单位的列表，长度为 repeat，median 用 statistics.median 计算）。
对 params.json 的 sizes 中的每个函数，按顺序用 time_it 对它的四个规模各重复测量 5 次以上，以 {"functions": {이름: [{"n", "samples", "median", "min"}, …]}}（占位符为函数名称）的形式写入 /root/svccs/measure/doubling.json。输入用 suspects.make_input(이름, n)（占位符为函数名称）生成。
在 /root/svccs/measure/ratios.json 中，为每个函数写入 {"ratios", "ratio", "exponent"}。ratios 是相邻两个规模的 min 之比，共三个（从小的 n 开始，保留三位小数）；ratio 是这三个比值（四舍五入之前）的中位数（保留三位小数）；exponent 是 log2(ratio)（保留两位小数）。
在 /root/svccs/measure/classes.json 中，把五个函数分类为 "linear" 或 "quadratic"（例如：{"dedupe": "…", …}）。
在 /root/svccs/measure/fixed.py 中编写 dedupe_fast(items)。它要返回与 suspects.dedupe 相同的值、相同的顺序，而且必须是线性的。不要修改收到的列表，并且要能接收非字符串的可哈希值。
对 compare_sizes 中的每个规模，用同一个输入生成器（make_input("dedupe", n)）分别对 suspects.dedupe（before）和 fixed.dedupe_fast（after）测量 5 次以上，并以 {"rows": [{"n", "before": {"samples", "median"}, "after": {"samples", "median"}, "speedup", "separated"}]} 的形式写入 /root/svccs/measure/compare.json。speedup 为 before 中位数 ÷ after 中位数（保留两位小数），separated 表示 after 中最大的样本是否小于 before 中最小的样本（true/false）。
在 /root/svccs/measure/forecast.json 中写入外推结果。使用第 7 步中最大的 n 所在的行；exponent_before 取第 4 步中 dedupe 的指数；before_s = before 중앙값 × (target_n ÷ n) ** exponent_before（占位符为 before 的中位数，保留三位小数）；after_s = after 중앙값 × (target_n ÷ n)（占位符为 after 的中位数，保留五位小数）；fits_before 和 fits_after 分别表示是否不超过 budget_s；并原样写入 target_n 和 budget_s。

参考

测量是在 Pod 与其他任务共享 CPU 期间进行的。如果在第 5 步出现“测量不支持该分类”之类的提示，请从第 3 步开始重测。
评分器会导入 bench.py 和 fixed.py。执行代码请放在 if __name__ == "__main__": 之下或单独的脚本里。
常见错误：把生成输入的时间也算进去；只测一次；在中位数的位置写平均值；把去重改成 set() 而丢失顺序。
产出会在会话结束后消失。需要的话请另行保存。

选出用来测量区间的时钟

用 time.get_clock_info 把 perf_counter 和 time 两种时钟的 monotonic、adjustable、resolution、implementation 写入 /root/svccs/measure/clock.json，并在 choice 中写出用于区间测量的时钟。

把 time.get_clock_info('perf_counter') 返回的对象的四个属性原样抄下来即可。adjustable 为 true 的时钟，在 NTP 或管理员把时钟往回拨时也会跟着倒退，因此两次读数之差可能为负数。

反复测量的测量工具

在 /root/svccs/measure/bench.py 中编写 time_it(fn, make_input, n, repeat=7)。评分器会传入一个很慢的 make_input 和一个很短的 fn，确认是否每次重复都重新生成输入，以及是否把生成输入的时间从耗时中扣除了。

时钟要在 make_input 结束之后、调用 fn 之前读取。中位数用 statistics.median，最小值用 min。如果多次使用同一份输入，会修改输入的函数从第二次开始就在做另一件事了。

把输入逐次翻倍来测量

对 params.json 的 sizes 中的五个函数，每个函数在四种规模下各用 time_it 测量 5 次以上，以 functions → 名称 → [{n, samples, median, min}] 的形式写入 /root/svccs/measure/doubling.json。

输入用 suspects.make_input(名称, n) 生成。用 lambda 传递时，如果不把循环变量 name 绑定为默认参数，所有 lambda 看到的都是最后一个名称。最大规模下的二次函数，一次可能要花将近 1 秒。

用比值读出指数

对每个函数，把 doubling.json 中相邻规模的 min 之比（三个）、它们的中位数以及 log2 指数写入 /root/svccs/measure/ratios.json。评分器会按相同规则用你的样本重新计算并对照。

t(2n)/t(n) ≈ 2^k，所以 k = log2(比值)。math.log 是自然对数，应使用 math.log2。看增长率时使用 min 的理由写在 timeit 文档里——较大的值通常是其他进程的干扰。

区分线性与二次

把五个函数分类为 linear 或 quadratic，写入 /root/svccs/measure/classes.json。评分器会与设计答案对照，也会检查你的测量在宽带范围内是否支持这个分类。

比值接近 2 是线性，接近 4 是二次。不要凭代码的样子判断——即使是双重循环，只要内层是常数次就是线性；只有一行的 in、insert(0, x)、反复拼接才会藏着二次复杂度。

保持顺序地修复去重

在 /root/svccs/measure/fixed.py 中编写 dedupe_fast(items)。评分器会检查：在变形输入上是否与原函数给出相同的值和相同的顺序，== 调用次数是否与输入成正比，以及在 20 万个元素上耗时是否没有按二次增长。

如果不用 list，而是用基于哈希的结构来询问“是否已经见过”，就是线性的。set 是无序集合，结果顺序会改变。dict 保持插入顺序（自 3.7 起是语言规范）。

用分布证明改进

对 compare_sizes 中的每个规模，用同一个输入生成器分别对 dedupe 和 dedupe_fast 测量 5 次以上，把 before、after 的样本和中位数、speedup、separated 写入 /root/svccs/measure/compare.json。

一对平均值会被一个异常样本拉走。两个分布互不重叠（after 最慢的值 < before 最快的值）是“不是噪声”的最简单证据。

外推到目标规模并与预算对照

用第 4 步的 dedupe 指数和第 7 步最大 n 的中位数，外推出 target_n 下改进前后的耗时，写入 /root/svccs/measure/forecast.json，并与 budget_s 对照。

t(target) ≈ t(n) × (target ÷ n)^k。改进后的部分，已在第 6 步确认是线性的（k = 1）。外推建立在同样的增长率会持续的假设上，所以结果只应读作“大致是几位数”。