别背大 O，把输入翻倍来测

一句话总结

“这个函数是 O(n)”不能靠背诵来说，而要靠测量来说。把输入翻倍后，看耗时变成几倍，就能暴露隐藏的二次复杂度；看反复测量得到的分布，就能分清“变快了”究竟是噪声还是真正的改进。

为什么需要它

在预发布环境（staging）里，100 条数据只需 0.1ms 的去重，到了生产环境遇到 5 万条数据就变成几秒，这种事很常见（示例）。代码一行都没有改，测试也全是绿灯。因为输入很小时，二次复杂度的函数也很快。问题不在于“有多快”，而在于“输入变多时它如何增长”，而这个问题无法靠一次测量来回答。

反过来，只看代码的样子来判断也会出错。双重循环但内层总是只循环三次，那就是线性的；没有循环，只有 if x not in seen: 这一行，但如果 seen 是 list，这一行就会从头扫描整个列表。TimeComplexity 维基以 CPython 为基准，把 list 的 x in s、insert 和中间元素的 pop 记为 O(n)，把 set 的 x in s 记为平均 O(1)（最坏 O(n)）。这里的 n 是容器当前所含的元素个数，如果在循环内被调用，开销还会相乘。

工作原理

倍增实验。 如果耗时大约是 c·n^k，那么 t(2n)/t(n) ≈ 2^k。比值接近 2 是线性，接近 4 是二次，接近 8 是三次。指数用 log2(比值) 来读。n log n 每翻一倍只会略高于 2，用这种方法很难与线性区分，所以本实验只区分线性和二次。规模要像 n、2n、4n、8n 这样多次放大，得到三个比值，并以其中位数作为代表——只看一对比值的话，一个噪声就会颠覆结论。

时钟。 time.perf_counter 是为测量短区间而提供最高分辨率的时钟，只有两次读数之差才有意义。在 CPython 中它是不会倒退的（monotonic）时钟。相反，文档写明 time.time() 在系统时钟被向后调整时，可能返回比之前更小的值。哪个时钟可以被调整，可以通过 time.get_clock_info() 的 adjustable 和 monotonic 直接查询。

重复与代表值。 同一段代码测七次，会得到七个不同的数字。timeit 文档指出，对重复结果求平均值和标准差没有多大用处。理由是：最小值是这台机器运行这段代码所能达到的下限，而较大的值通常不是 Python 造成的，而是其他进程的干扰。因此本实验在看代码本身的增长率（倍增比率）时，用最小值相除。而在对比改进前后并汇报时，则同时写出中位数和分布。正如 statistics.median 文档所述，中位数是不易被异常值动摇的代表值，而两个分布互不重叠（改进后最慢的样本也比改进前最快的样本更快），是比一对平均值强得多的证据。timeit 默认在测量期间关闭垃圾回收，默认重复次数为 5。

测量工具还必须遵守一件事：不测量生成输入的时间。如果把线性的输入生成时间混进去，二次函数的比值就会低于 4，从而掩盖二次复杂度。而且有些函数会修改输入，所以每次重复都要重新生成输入。

三种隐藏的二次复杂度。 对 list 的 in、list.insert(0, x)，以及反复拼接不可变序列。通用序列操作文档写道，拼接不可变序列总会产生新对象，所以反复拼接的开销相对于总长度是二次的，并给出了替代方案：str 用 str.join() 或 io.StringIO，bytes 用 bytes.join()、io.BytesIO、bytearray。str 的 a += b 在某些情况下会被 CPython 优化，但 PEP 8 指出，这种优化即使在 CPython 中也很脆弱，而在不使用引用计数的实现里根本不存在，所以不要依赖它。这就是本实验测量 bytes 而不是 str 的原因。

修改时要守住的事。 把去重改成 list(set(items)) 会变快，但 set 是无序集合，结果的顺序会改变。dict 自 3.7 起保持插入顺序就是语言规范，所以 dict.fromkeys(items) 会保持首次出现的顺序。变快的函数如果给出了不同的答案，那就不是改进，而是 bug。

在现场相遇的样子

如果性能优化 PR 里写着“在本地测了一次，快了 12%”，这个数字还什么都没有证明。必须同时追问：在相同条件下测了几次，前后分布是否重叠，以及输入变成十倍会怎样。用倍增实验得到指数之后，就能外推“现在 8 千条要 0.2 秒，10 万条要几秒”，再把这个数字与预算对照，决定现在是否要修。外推建立在同样的增长率会持续下去的假设之上，在数据超出 CPU 缓存的地方，比值本身可能发生变化——这一点由“计算机组成”课程来讲。找出哪里慢的性能分析（cProfile 的 tottime、cumtime）由“CPU 与内存泄漏的判定”课程负责，给整个服务施加负载、用百分位判定回归的工作，则由“压力测试”课程讲解。本模块处于它们之间，负责测量单个函数的增长率。

下一项实验要做什么

先直接向 Pod 查询两种时钟的性质，再做出能执行重复、中位数、最小值的测量工具。对五个隐藏了复杂度的函数，在四种规模下测量，求出比值和指数，区分线性与二次。修复最常见的二次复杂度——去重，并保持原有顺序；用分布来比较改进前后；再外推 10 万条数据要花多少秒，并与预算对照。