让 Python 再快一点

常数因子从哪来

第 28 课讲的是复杂度的量级：O(n^2) 和 O(n \log n) 差的是指数。这一课讲另一件事——同一个量级里，写法不同也能差出几百倍。

第 2 课量过：本机一次循环大约 20 纳秒，每秒约 5 \times 10^7 次。可那个「一次循环」是理想情况。真写起来，一次循环里可能有函数调用、属性查找、全局名查找、容器扫描，每一样都要花时间，加起来就是常数因子。

常数因子不是学术问题。一道题正解 O(n)、n = 10^6，按尺子算 0.02 秒，稳过。可如果在一次循环里调了个函数，实际可能翻倍；如果在循环里对一个列表做 in，那已经不是常数问题了，是你把复杂度写坏了。

别猜，先量出瓶颈

「不测就猜瓶颈在哪」是这一课的第一个坑。看这样一段场景：

import random

N = 200000
ARR = [random.Random(3).randint(0, 10 ** 6) for _ in range(N)]
KEYS = [random.Random(5).randint(0, 10 ** 6) for _ in range(2000)]

三段分别做三件事：把 20 万个元素装进集合、排序这 20 万个元素、做 2000 次「这个键在不在数组里」。凭直觉猜，哪一段最慢？

多数人会指向那两个 20 万规模的。实测是反的（本机实测，取中位数）：

C 段看着最无害——只有 2000 次循环，比 A、B 的 20 万小两个数量级。可它要 1.9 秒，是 A 的 950 倍、B 的 3000 倍。

原因不全是常数因子，主要是复杂度：列表的 in 是线性扫描，20 万乘 2000 是 4 \times 10^8 次比较；集合的 in 平均一步。所以「哪一段慢」不能看代码形状，要看每一段各执行多少次操作。

把这件事用次数算出来——不看时间，只看语句执行次数：

n_small = 30
n_keys = 100000
n_big = 100000

inner_ops = n_small * n_small        # 两重循环，各 30
list_in_ops = n_keys * n_big         # 列表的 in 是线性扫描
set_in_ops = n_keys * 1              # 集合的 in 平均一步
print('   三段各做多少次操作（按语句执行次数算，不看代码长什么样）：')
print(f'     两重循环，各 30        ：{inner_ops:>18,} 次内层操作')
print(f'     一重循环里的 in，列表  ：{list_in_ops:>18,} 次比较')
print(f'     一重循环里的 in，集合  ：{set_in_ops:>18,} 次比较')
print(f'   看着凶的那段（两重循环）比看着无害的那段（一个 in）少 '
      f'{list_in_ops / inner_ops:.2e} 倍的操作。')

   三段各做多少次操作（按语句执行次数算，不看代码长什么样）：
     两重循环，各 30        ：               900 次内层操作
     一重循环里的 in，列表  ：    10,000,000,000 次比较
     一重循环里的 in，集合  ：           100,000 次比较
   看着凶的那段（两重循环）比看着无害的那段（一个 in）少 1.11e+07 倍的操作。

两重循环（看着吓人）只有 900 次操作；一重的 in 写在列表上（看着无害）是 10^{10} 次。 差一千万倍。

所以定位瓶颈的次序是：先数每段跑多少次 → 再估每次有多贵 → 最后用计时确认。

循环里少做重复的事

同一段代码，把「每轮都要重新算一遍」的东西提到循环外面，就是最基础的一招。下面 🅐 是反例、🅑 是正例——注意看 size() 被调了几次：

class Counter:
    """一个会自己数「被调用了几次」的对象。"""

    def __init__(self):
        self.n = 0

    def size(self):
        self.n += 1
        return 1000


def check_in_condition(cnt):
    """把 cnt.size() 写在 while 的条件里。"""
    i = 0
    total = 0
    while i < cnt.size():
        total += i
        i += 1
    return total


def check_hoisted(cnt):
    """先把长度取出来，循环里不再问。"""
    limit = cnt.size()
    i = 0
    total = 0
    while i < limit:
        total += i
        i += 1
    return total


c1, c2 = Counter(), Counter()
r1, r2 = check_in_condition(c1), check_hoisted(c2)
print(f'   两版答案一致吗: {r1 == r2}（都是 {r1}）')
print(f'   写在 while 条件里：size() 被调用了 {c1.n:>5} 次')
print(f'   提到循环外面  ：size() 被调用了 {c2.n:>5} 次')

   两版答案一致吗: True（都是 499500）
   写在 while 条件里：size() 被调用了  1001 次
   提到循环外面  ：size() 被调用了     1 次

答案完全一样，调用次数差一千倍。 而且 while i < cnt.size() 是 n + 1 次而不是 n 次——最后一次是退出循环前那次失败的比较，很容易漏算。

同样的道理适用于循环体里所有不随下标变化的表达式：len(a)、obj.attr、a.b.c、反复算同一个常量。全部提到循环外面。

全局名与局部名

这一节要给你一个反例，因为它跟很多教程讲的不一样。

「局部变量比全局变量快」是常被引用的规律。本机实测下来，它是真的，但幅度很小：

只有 6% 到 13%。 而第一次量的时候（n = 10^6、只跑 3 次）我量到的比值是 1.00——完全看不出差别，因为噪声比效应还大。

原因是新版本的 CPython 给全局名查找加了内联缓存，LOAD_GLOBAL 不再每次都真去查字典。所以这条规律没有过时，但已经从「重要的一招」退化成「顺手可以做的事」。

这对你的取舍有直接影响：如果瓶颈分析指到别处（比如一个列表的 in，差 230 倍），把名字改成局部变量省下那 10% 是白费力气。 先量，再决定值不值得动。

输入输出最便宜

有一类优化几乎不需要动脑筋，收益却最大：读入。

逐行 input() 每读一行都要走一次函数调用加一次解析；把整个输入一次读进来、再 split() 成 token，同样的活只让 C 层做一遍。实测读 10^6 行整数：

7.9 倍，而两种读法得到的数字完全一样。输入越大差距越明显，因为逐行 input() 的开销是每行一次，整体读只有一次调用。

真实代码的第二行是 data = sys.stdin.buffer.read().split()，剩下三行照写。把那行换成一个写死的字节串，整段就能单独跑起来看效果：

import io

RAW = b'4\n3 1 4 1\n'                        # 假装这是题目给的输入

data = io.BytesIO(RAW).read().split()        # 真代码这里是 sys.stdin.buffer.read().split()
it = iter(data)
n = int(next(it))
a = [int(next(it)) for _ in range(n)]
print(f'   读到 n = {n}，数组 = {a}')

   读到 n = 4，数组 = [3, 1, 4, 1]

能用内置就用内置

第 2 课提过一句「内置函数是 C 写的」。这一课把它量出来。同样对 10^6 个元素求和：

差距来自循环本身：手写版每轮要做一次 FOR_ITER、一次加法、一次 STORE_FAST，全在 Python 层；sum(a) 的整个循环在 C 里跑，Python 只付一次调用的钱。

排序上差距更大。n = 3000：

这一栏要分开看：1134 倍里，绝大部分来自复杂度（O(n \log n) 对 O(n^2)），只有一小部分来自常数。 别把这一行当成「内置比手写快一千倍」的证据——它证明的是「别手写排序」。

该用的内置还有一批：max、min、any、all、sorted、list.sort、map、sum、collections.deque、bisect、itertools.accumulate。

换个容器更值钱

前面那段 1.9 秒的瓶颈，修法不是改循环写法，是换容器。同一批数据、同一件事，只把列表换成集合：

230 倍，答案一模一样。

这就是本课最重要的一条取舍：换数据结构通常比抠语法值钱得多。 抠一个局部变量省 10%，换容器省 23000%；而且换容器是改一行，抠语法要改一片。

类似的对应关系还有：

• 反复取最小 → 别用 min(a)，用 heapq
• 反复查在不在 → 别用列表，用 set 或 dict
• 反复在队首删除 → 别用 list.pop(0)，用 collections.deque
• 反复求区间和 → 别每次重算，用前缀和

查表与分支

「用查表代替分支判断」也是一条常被引用的规律。它成立，但要看清前提。

下面这张表是同一件事的两种写法（10^6 个值，两边答案逐字一致），只改分支链的长度：

看最后两列的形状，而不是倍数：

• if/elif 链的耗时跟着分支数长：2 个分支 0.0189，16 个分支 0.0749，差不多线性。
• 查表的耗时几乎不动：不管 2 项还是 16 项，都在 0.0175 上下。

因为 if/elif 是一路比下来的，第 16 个分支平均要比 8 次；查表是一次索引。这就是「O(k) 对 O(1)」在小 k 上的样子。

所以怎么选：

• 2 到 3 个分支：差别在噪声边缘（1.06 到 1.30 倍）。按可读性选就行，为了这 6% 把代码改成查表不值得。
• 8 个以上分支：查表稳赢，2.65 倍起。分支越多越该换。

大循环别用递归

第三个坑：用递归写本来该迭代的大循环。实测 n = 900 求和：

6.7 倍来自每层调用都要建一个栈帧。但比速度更硬的问题是上限——递归深度到不了任意大：

def sum_rec(a, i=0):
    if i == len(a):
        return 0
    return a[i] + sum_rec(a, i + 1)


def sum_iter(a):
    t = 0
    for x in a:
        t += x
    return t


for n in (900, 990, 995, 996, 997, 998, 999, 1000):
    a = list(range(n))
    try:
        r = sum_rec(a)
        print(f'   n = {n:>4}: 递归版跑通，和 {r}，迭代版和 {sum_iter(a)}，一致 {r == sum_iter(a)}')
    except RecursionError:
        print(f'   n = {n:>4}: 递归版 RecursionError')

   n =  900: 递归版跑通，和 404550，迭代版和 404550，一致 True
   n =  990: 递归版跑通，和 489555，迭代版和 489555，一致 True
   n =  995: 递归版跑通，和 494515，迭代版和 494515，一致 True
   n =  996: 递归版跑通，和 495510，迭代版和 495510，一致 True
   n =  997: 递归版跑通，和 496506，迭代版和 496506，一致 True
   n =  998: 递归版跑通，和 497503，迭代版和 497503，一致 True
   n =  999: 递归版 RecursionError
   n = 1000: 递归版 RecursionError

边界就在 998 和 999 之间——跟第 12 课、第 17 课量到的是同一个数（默认上限 1000，主模块本身占一层）。

所以规则很简单：深度靠 n 决定的递归，一律改迭代，或者用显式栈。深度只跟 \log n 有关的（比如分治、树遍历）可以留着。

优化不许改答案

第二个坑是为了优化牺牲正确性。这一课教的每一招都会改代码，改代码就可能改错。所以每改一处，都要回验答案：

import random

random.seed(11)
bad_iter = 0
bad_hoist = 0
trials = 300
for _ in range(trials):
    n = random.randint(0, 50)
    a = [random.randint(-9, 9) for _ in range(n)]
    if sum_iter(a) != sum(a):
        bad_iter += 1
    if check_in_condition(Counter()) != check_hoisted(Counter()):
        bad_hoist += 1
print(f'   {trials} 组随机数据上，优化版与原版答案不一致的组数：')
print(f'      手写循环 vs 内置 sum            : {bad_iter} 组')
print(f'      size() 写在条件里 vs 提到外面   : {bad_hoist} 组')

   300 组随机数据上，优化版与原版答案不一致的组数：
      手写循环 vs 内置 sum            : 0 组
      size() 写在条件里 vs 提到外面   : 0 组

0 组。 这就是第 15 课那套对拍：优化后的版本与被替换掉的版本，在同一批随机数据上必须逐字一致，边界包含空数组和负数。

顺序不能颠倒：先让它对，再让它快，而且每快一次都要重新证明它对。 反过来做（先快再想法子对）会把你带进「改一处、坏一处、看不出来」的泥潭。

这一课用到的判断

• 先量再动。 不测就猜瓶颈，猜错的概率比你想象的高——本课那段 1.9 秒的瓶颈，看着是整段里最无害的。
• 定位瓶颈看次数，不看形状。 两重循环各 30 只有 900 次操作；一重的 in 写在列表上是 10^{10} 次。差一千万倍。
• 换容器比抠语法值钱。 列表换集合 230 倍、改一行；全局名改局部名 6% 到 13%、改一片。先做前者。
• 「局部变量比全局快」成立但很小（本机实测 6% 到 13%，首轮甚至量到 1.00）。新 CPython 给全局查找加了内联缓存，这条规律没失效，但已经不值得优先动它。
• 读入是最便宜的提速。 整体 read().split() 比逐行 int(input()) 快 7.9 倍（10^6 行），输出同理，攒起来一次打印。
• 能用内置就用内置。 求和 4.8 倍。但 sorted 快 1134 倍那一栏主要是复杂度的功劳，别记成常数。
• 查表的值随分支数长，查表的耗时不动。 2 到 3 个分支按可读性选；8 个以上查表稳赢 2.65 倍起。
• 深度跟着 n 长的递归一律改迭代。 不只因为慢 6.7 倍，更因为本机在 n = 999 就越界（n = 998 还行）。
• 每改一处都回验。 对拍的数据要按题目上限的量级生成，小样例测不出容器换了等于没换。
• 基准测试写错会得出刚好相反的结论，而且看起来一样可信。 两个版本除了要比的那一点，其余必须严格一样——本课那个「查表反而慢 12%」就是我自己写错量出来的。

• Python 官方文档 · profile 与 pstats官方 · cProfile 的用法，比手工计时更系统地找瓶颈
• Python 官方文档 · timeit官方 · 小段代码计时的标准工具，本课那些中位数就是用它这类做法量的
• Python Wiki · PythonSpeed社区 · 常数优化的常见清单（部分条目较旧，要自己复测）
• 第 2 课：同一道题，两种写法本课那把尺子与「内置是 C 写的」那句话的出处
• 第 15 课：对拍：用小数据抓错本课「每改一处都回验」用的就是那一套
• 第 28 课：看数据规模挑算法先定量级再谈常数，两课的顺序不能反