🏠 总目录📚 本教程 07 · 把循环改写成数组运算 ← →

NUMPY / 07 · 07 · 把循环改写成数组运算:六个套路

这段循环,真正想把哪些数据合在一起?

不要先找一个长得像循环的 API。先辨认你正在维护的关系,再选数组操作。

你能按任务找到六类改写入口,并保留规模、内存与输入边界的检查。

patterns 机制示意六条是原文六个任务的入口图,不表示复杂度或性能排名。Top-K、分桶与窗口的边界仍须逐一核对。累计 / 分组cumsum / bincount候选 / 窗口argpartition / sliding...分桶 / 相邻变化searchsorted / diff
六条是原文六个任务的入口图,不表示复杂度或性能排名。Top-K、分桶与窗口的边界仍须逐一核对。
阅读范围、用时与原有实验记录
实验记录怎么读

本页原有耗时、内存、报错和环境值保留为原文记录;本轮内容审校未逐项复跑这些实验。版本、硬件、数据和测量方法都会影响结果,示例中的倍数也不是保证。需要复现时先核对依赖版本,再在同一输入下比较。

⏱ 66 分钟 | ⭐ 前六章讲的是「为什么」和「怎么读」,这一章是唯一一章讲「拿到一个循环,手怎么动」

01 / 完整解释

先认出循环在维护什么。

🎯 一句话

大多数循环之所以能改写,是因为它其实在做六件事之一:累积、分组、取前 k 个、开窗、查区间、找相邻变化。 认出是哪一件,对应的函数就只有一个。认不出来的那些,本章最后一节告诉你别硬改。

🧩 一、动手之前,先问三个问题

上一章讲完索引,工具箱就齐了。但不是所有循环都该改写,先用这三个问题筛一遍:

问题 答「是」的话 答「否」的话
① 第 i 次迭代要用到第 i−1 次的结果吗? 只能用专门的累积函数(cumsum / cumprod / np.maximum.accumulate),没有对应函数就别改 随便改
② 改完的中间体有多大? 中间体比原数组大几十倍时,要么分块,要么放弃 随便改
③ 这个循环一次跑几个元素? 几十个:改了也没用,NumPy 每次调用有固定开销 上万个:值得改

⭐ 第 ① 条最容易判错。「用到上一次的结果」不等于「必须写循环」——前缀和明明是顺序依赖,np.cumsum 照样一行搞定。 正确的判据是:这个顺序依赖有没有现成的 ufunc accumulate。有就用,没有(比如「每步的结果决定下一步读哪个下标」)就老实写循环。

⚠️ 第 ③ 条不是玩笑。下面所有倍数都是在 N = 200,000 上测的;N = 100 时数组版经常更慢,因为你花在建临时数组上的时间比省下来的还多。

02 / 完整解释

六种关系,六个数组入口。

🧩 二、① 累积:cumsum / cumprod / accumulate

长什么样:循环里有一个「累加变量」,每轮更新它并记下来。

先跟着两行数据累加

两家门店各记录三天的售出件数。甲店是 [60, 70, 10],乙店是 [20, 30, 40]。现在要知道每家店到每天结束时一共卖了多少件,最后一天的总数只是三个答案中的一个。

同一行的累计值会传到下一天
门店第 1 天第 2 天第 3 天
甲0 + 60 = 6060 + 70 = 130130 + 10 = 140
乙0 + 20 = 2020 + 30 = 5050 + 40 = 90

累积和(Cumulative Sum)保留每一步的合计。循环版每到一行就把合计清零,读一格,加一格,存一格。axis=1 指定沿列方向推进,保留 (2, 3) 形状。改成 axis=0 会沿门店方向推进,第二行变为 [60+20, 70+30, 10+40] = [80, 100, 50]。省略 axis 则会把两行接成一条长度为 6 的序列,读到乙店第一天时会从甲店的 140 继续加,得到 160。

import numpy as np

sales = np.array([[60, 70, 10], [20, 30, 40]], dtype=np.int8)
loop_rows = []
for row in sales:
    total = 0
    running = []
    for value in row:
        total += int(value)
        running.append(total)
    loop_rows.append(running)

wide = np.cumsum(sales, axis=1, dtype=np.int64)
narrow = np.cumsum(sales, axis=1, dtype=np.int8)
assert wide.tolist() == loop_rows
print("逐行", wide.shape, wide.tolist())
print("沿门店", np.cumsum(sales, axis=0, dtype=np.int64).tolist())
print("摊平", np.cumsum(sales, dtype=np.int64).tolist())
print("窄类型", narrow.tolist())

四行输出依次是 (2, 3) [[60, 130, 140], [20, 50, 90]]、[[60, 70, 10], [80, 100, 50]]、[60, 130, 140, 160, 190, 230] 和 [[60, -126, -116], [20, 50, 90]]。

int8 能存每一笔售出件数,但累加器(保存当前合计的变量)只能表示 −128 到 127。甲店第二天的 130 按 256 回绕成 130 − 256 = −126,第三天再加 10 得到 −116。dtype=np.int64 让这次运算用较宽的累加器,结果也用该类型存储。选型时要覆盖累计值可能达到的范围,见 第 08 章和 NumPy 的 cumsum 文档。

下面用同一个一维循环思路测量较大输入,先比较结果,再比较耗时。

import numpy as np
import timeit

rng = np.random.default_rng(0)
N = 200_000
x = rng.random(N)

def loop_cumsum(x):                      # 循环版:一个累加变量 + 逐个写回
    out = np.empty(len(x))
    s = 0.0
    for i in range(len(x)):
        s += x[i]
        out[i] = s
    return out

print("最大差", np.abs(loop_cumsum(x) - np.cumsum(x)).max())   # ⭐ 先对正确性

t_loop = min(timeit.repeat(lambda: loop_cumsum(x), number=1, repeat=5))
t_arr  = min(timeit.repeat(lambda: np.cumsum(x),   number=1, repeat=5))
print(f"循环 {t_loop*1e3:.2f} ms | np.cumsum {t_arr*1e3:.3f} ms | {t_loop/t_arr:.0f}x")

要点

最大差 0.0

循环 25.59 ms | np.cumsum 1.103 ms | 23x

常见的逐元素二元运算也可以用 .accumulate 沿一根轴保留中间结果。下表以一维输入为例。换成多维输入时,np.add.accumulate 默认沿轴 0,np.cumsum 默认摊平,比较时应指定相同的轴。

循环在做 写成
累加 np.cumsum(x) / np.add.accumulate(x)
累乘 np.cumprod(x)
「到目前为止的最大值」 np.maximum.accumulate(x) ⭐ 回撤计算就是这个
「到目前为止是不是一直为真」 np.logical_and.accumulate(m)

浮点累积也有舍入。 cumsum 保存顺次相加的每一步,末值可能和采用不同加法顺序的 sum 不同。只需要最终合计时,可以考虑精度更高的 math.fsum;如果要每个前缀的合计,需要逐个核对允许的误差。

🧩 三、② 分组求和:np.bincount

长什么样:循环里有个 dict,按某个 key 往里 +=。

先把三笔记录放进四个组

沿用甲店的三笔销售记录 x=[60, 70, 10]。假设每笔各属于一个商品组,按相同顺序标记 g=[2, 0, 2]。报表约定固定列出 0 到 3 四组,即使某组本次没有记录也留一格。

先把四格清零,再按组号更新对应的格
当前操作组 0组 1组 2组 3
初始值0000
60 件 → 组 2000 + 60 = 600
70 件 → 组 00 + 70 = 700600
10 件 → 组 270060 + 10 = 700

np.bincount 以组号作为结果的下标。只传 g 时每遇到一笔就加 1,得到各组记录数。再传入同长度的 weights=x 时,每笔加的是售出件数。这里最大组号是 2,默认结果有 3 格,缺少中间的组 1 会填 0,末尾的组 3 要由 minlength=4 补齐。

import numpy as np

g = np.array([2, 0, 2], dtype=np.intp)
x = np.array([60, 70, 10], dtype=np.int64)
loop_totals = [0] * 4
for group, units in zip(g, x):
    loop_totals[group] += int(units)

totals = np.bincount(g, weights=x, minlength=4)
counts = np.bincount(g, minlength=4)
assert totals.tolist() == loop_totals
print("各组总量", totals.tolist(), totals.dtype)
print("各组笔数", counts.tolist())
print("长度下限设为 2", np.bincount(g, minlength=2).tolist())

输出依次是 [70.0, 0.0, 70.0, 0.0] float64、[1, 0, 2, 0] 和 [1, 0, 2]。minlength=2 仍要给组 2 留位置。这个非空示例中,即使用整数权重也得到浮点和;需要精确保留大整数时,应改用容量足够的整数累加器。

下面的计时例把固定长度的累加表换成字典循环对照,数组版仍按组号更新一格。

import numpy as np
import timeit

rng = np.random.default_rng(0)
N, G = 200_000, 1000
g = rng.integers(0, G, N)          # 组号,取值 0..999
x = rng.random(N)

def loop_group(g, x):                    # 循环版:dict 里 +=
    d = {}
    for gi, xi in zip(g, x):
        d[int(gi)] = d.get(int(gi), 0.0) + float(xi)
    return d

def arr_group(g, x):                     # 数组版:一行
    return np.bincount(g, weights=x, minlength=G)

d, a = loop_group(g, x), arr_group(g, x)
print("最大差", max(abs(d[k] - a[k]) for k in d))

t_loop = min(timeit.repeat(lambda: loop_group(g, x), number=1, repeat=5))
t_arr  = min(timeit.repeat(lambda: arr_group(g, x),  number=1, repeat=5))
print(f"循环 {t_loop*1e3:.2f} ms | np.bincount {t_arr*1e3:.3f} ms | {t_loop/t_arr:.0f}x")

要点

最大差 0.0

循环 35.18 ms | np.bincount 0.283 ms | 124x

在这次测量里,数组版省掉了 Python 循环中的字典查找,按组号更新结果数组。组号越稀疏,空格越多,也要把结果数组的空间算进账单。

三个必须知道的细节:

细节 说明
minlength 非空输入的输出长度是 max(minlength, 最大组号 + 1)。固定报表时可传入约定的组数,并另外验证组号没有超出报表范围。
组号必须是非负整数 组号必须是一维非负整数,负组号会报错。结果长度取决于最大组号,两条组号为 0 和 1000000 的记录也要容纳 1000001 格。遇到字符串或稀疏 ID,可用 np.unique(keys, return_inverse=True) 得到原标签和连续的组号。
不带 weights 就是计数 np.bincount(g) 得到每组记录数。算组均值时让加权和与计数使用同一组号和长度,只对计数大于 0 的组做除法。空组没有均值。

和上一章的关系。 b[[1,1,1]] += 1 只加一次,np.add.at(b, [1,1,1], 1) 才加三次。组号是一维非负整数时,bincount 可以一次返回各组的计数或加权和。更多输入条件见 NumPy 的 bincount 文档。

🧩 四、③ Top-K:np.argpartition

长什么样:np.argsort(-x)[:k]。⚠️ 它不是循环,但它是站内出现频率最高的一个「多做了很多功」的写法——为了拿前 10 个,把 20 万个全排了一遍。

import numpy as np
import timeit

rng = np.random.default_rng(0)
N, k = 200_000, 10
x = rng.random(N)

def topk_sort(x, k):                     # 全排序再切
    return np.argsort(-x)[:k]

def topk_part(x, k):                     # 只保证「前 k 个在前面」,不保证它们有序
    if not 0 <= k <= len(x):
        raise ValueError("k out of range")
    if k == 0:
        return np.array([], dtype=np.intp)
    idx = np.argpartition(-x, k - 1)[:k]
    return idx[np.argsort(-x[idx])]      # ⭐ 需要有序的话,再对这 k 个排一次

print("集合一致", set(topk_sort(x, k).tolist()) == set(topk_part(x, k).tolist()))

t_sort = min(timeit.repeat(lambda: topk_sort(x, k), number=1, repeat=5))
t_part = min(timeit.repeat(lambda: topk_part(x, k), number=1, repeat=5))
print(f"argsort {t_sort*1e3:.2f} ms | argpartition {t_part*1e3:.3f} ms | {t_sort/t_part:.1f}x")

要点

集合一致 True

argsort 9.50 ms | argpartition 2.148 ms | 4.4x

argpartition 的 kth 从 0 数起,分区内部不保证顺序。对能够安全取负的有限一维数组,可用 np.argpartition(-x, k - 1)[:k] 取最大的 k 个元素的下标(1 ≤ k ≤ len(x)),再只对这些元素排序。k=0 直接返回空结果。若可能出现 NaN 或第 k 大的分数并列,先定义选择规则。

本节计时样本是可安全取负的浮点数。若 x 是 uint8,250 取负后回绕成 6,最小值不再对应原数组的最大值。固定宽度有符号整数的最小值也有取负溢出风险。可以直接在原值上以 len(x) - k 分区,取右侧 k 个,再按原值排序。

import numpy as np

values = np.array([0, 250, 2], dtype=np.uint8)
k = 1
negated = -values
wrong = np.argpartition(negated, k - 1)[:k]
right = np.argpartition(values, len(values) - k)[-k:]
right = right[np.argsort(values[right])[::-1]]
print(negated.tolist(), values[wrong].tolist(), values[right].tolist())
# [0, 6, 254] [0] [250]

🧩 五、④ 滑窗:sliding_window_view

长什么样:for i in range(N-w+1): out[i] = f(x[i:i+w])。

import numpy as np
import timeit
from numpy.lib.stride_tricks import sliding_window_view

rng = np.random.default_rng(0)
N, w = 200_000, 50
x = rng.random(N)

def loop_window(x, w):                   # 循环版:切一片算一次均值
    return np.array([x[i:i+w].mean() for i in range(len(x) - w + 1)])

def arr_window(x, w):                    # 数组版:一次性铺开成 (N-w+1, w)
    return sliding_window_view(x, w).mean(-1)

print("最大差", np.abs(loop_window(x, w) - arr_window(x, w)).max())

t_loop = min(timeit.repeat(lambda: loop_window(x, w), number=1, repeat=5))
t_arr  = min(timeit.repeat(lambda: arr_window(x, w),  number=1, repeat=5))
print(f"循环 {t_loop*1e3:.2f} ms | sliding_window_view {t_arr*1e3:.3f} ms | {t_loop/t_arr:.0f}x")

v = sliding_window_view(x, w)
print("展开后形状", v.shape, "| 与原数组共享内存", np.shares_memory(v, x))
print("如果真复制要占", round(v.nbytes/1024**2, 1), "MiB;实际 x 只占",
      round(x.nbytes/1024**2, 1), "MiB")

要点

最大差 0.0

循环 850.47 ms | sliding_window_view 5.950 ms | 143x

展开后形状 (199951, 50) | 与原数组共享内存 True

如果真复制要占 76.3 MiB;实际 x 只占 1.5 MiB

⭐ 最后两行是这一节真正的重点:(199951, 50) 这个形状看着像把数据复制了 50 份,但 shares_memory 是 True ——它没有复制任何东西,只是给同一块内存换了一套读法。76.3 MiB 是「如果真复制」的账,实际开销是 0。

为什么能这样,是 05 · 内存布局与 stride 那一章的正题;这里只需要知道它免费。

⚠️ 两个坑:

  • 它返回的是只读视图。想改就先 .copy(),那时候 76 MiB 才真的会花掉。
  • ⚠️ 后面接的操作可能会让它变贵。.mean(-1) 不复制,但 sliding_window_view(x, w).copy() 或者把它喂给某些需要连续内存的函数,就会当场展开成 76 MiB。

🧩 六、⑤ 分桶:np.searchsorted

长什么样:循环里对每个元素做二分查找,或者一串 if / elif 判断落在哪个区间。

import numpy as np
import timeit
from bisect import bisect_right

rng = np.random.default_rng(0)
N = 200_000
edges = np.array([0.0, 0.1, 0.25, 0.5, 0.75, 0.9, 1.0])   # ⭐ 必须已排序
x = rng.random(N)

def loop_bucket(x, edges):               # 循环版:一个一个 bisect
    e = edges.tolist()
    return np.array([bisect_right(e, xi) for xi in x])

def arr_bucket(x, edges):                # 数组版:一次全查完
    return np.searchsorted(edges, x, side="right")

print("完全一致", np.array_equal(loop_bucket(x, edges), arr_bucket(x, edges)))

t_loop = min(timeit.repeat(lambda: loop_bucket(x, edges), number=1, repeat=5))
t_arr  = min(timeit.repeat(lambda: arr_bucket(x, edges),  number=1, repeat=5))
print(f"循环 {t_loop*1e3:.2f} ms | np.searchsorted {t_arr*1e3:.3f} ms | {t_loop/t_arr:.0f}x")

要点

完全一致 True

循环 61.14 ms | np.searchsorted 6.436 ms | 9x

⚠️ side 那个参数决定边界归左还是归右:值正好等于某个边界时,"left" 把它算进左边那个桶(和 0.49 同桶),"right" 算进右边(和 0.51 同桶)。等值样本多的时候(比如大量 0),这一个字母会改变一整个桶的大小。

⭐ searchsorted 不止能分桶。它的本质是「在一个已排序数组里,问这些值该插在哪」,所以还能做:把一批 ID 映射到它们在排序表中的位置、两个有序数组求交、找最近邻的那个刻度。

🧩 七、⑥ 找相邻变化:diff + flatnonzero

长什么样:循环比较 x[i] 和 x[i+1],记下不一样的位置。游程编码、找变号点、找状态切换点都是这一类。

import numpy as np
import timeit

rng = np.random.default_rng(0)
N = 200_000
y = rng.normal(size=N)                   # 有正有负的序列

def loop_sign(y):                        # 循环版:比较相邻两个
    out = []
    for i in range(len(y) - 1):
        if (y[i] < 0) != (y[i+1] < 0):
            out.append(i)
    return np.array(out)

def arr_sign(y):                         # 数组版:signbit -> diff -> 非零位置
    return np.flatnonzero(np.diff(np.signbit(y)))

print("完全一致", np.array_equal(loop_sign(y), arr_sign(y)), "| 变号次数", len(arr_sign(y)))

t_loop = min(timeit.repeat(lambda: loop_sign(y), number=1, repeat=5))
t_arr  = min(timeit.repeat(lambda: arr_sign(y),  number=1, repeat=5))
print(f"循环 {t_loop*1e3:.2f} ms | flatnonzero+diff {t_arr*1e3:.3f} ms | {t_loop/t_arr:.0f}x")

要点

完全一致 True | 变号次数 100527

循环 296.44 ms | flatnonzero+diff 0.706 ms | 420x

⭐ 这个套路的心法是「把状态变成布尔数组,再看它哪里跳变」:

想找 写法
变号位置 np.flatnonzero(np.diff(np.signbit(y)))
值发生变化的位置(游程边界) np.flatnonzero(np.diff(a) != 0)
每段游程的长度 在上面的边界数组两头补 -1 和 len(a)-1,再 np.diff
布尔序列里连续 True 的段 np.diff(m.astype(np.int8)),+1 是起点、-1 是终点

⚠️ flatnonzero(d) 给的是 d 的下标,不是原数组的下标。d = np.diff(y) 比 y 短 1,d[i] 描述的是 y[i] 和 y[i+1] 之间——所以「变化发生在 y 的第 i+1 个」。差这个 1 是本套路唯一的高频错误。

03 / 完整解释

最后才谈速度与代价。

🧩 八、一张表:六个套路的倍数

⚠️ 看倍数,不要看绝对耗时。 下面是同一台笔记本(Windows 11 · Python 3.13.14 · NumPy 2.4.6 · 无 GPU 参与)上 N = 200,000、timeit.repeat(number=1, repeat=5) 取 min、三次独立进程跑出来的区间。这台机器会热降频,所以给区间不给单点。

套路 循环版 数组版 循环 ms 数组 ms 倍数(三次)
① 累积 累加变量 + 逐个写回 np.cumsum 23.6 – 39.9 1.10 – 1.37 20 – 29x
② 分组求和 dict 里 += np.bincount(g, weights=x) 34.7 – 43.9 0.28 – 0.32 120 – 137x
③ Top-K(k=10) np.argsort(-x)[:10] np.argpartition(-x,10)[:10] 7.0 – 14.3 1.98 – 2.50 3.5 – 5.7x
④ 滑窗均值(w=50) for + 切片 .mean() sliding_window_view(x,50).mean(-1) 683 – 940 5.5 – 7.7 89 – 170x
⑤ 分桶 for + bisect np.searchsorted 39.0 – 61.1 4.85 – 6.44 8 – 10x
⑥ 找变号位置 for + 比较相邻 np.flatnonzero(np.diff(np.signbit(y))) 296 – 306 0.68 – 0.93 320 – 450x

⭐ 你的绝对耗时一定和上表不同,看量级和倍数就行。 同一台机器上三次跑,④ 的倍数就在 89x 和 170x 之间摆——这不是测量出错,是笔记本降频。真要给出可比的数字,得用固定频率的机器多轮取分位数,那套口径归《Python》板块的性能剖析章。

⚠️⚠️ ③ 只有 3.5–5.7x,这个数没有粉饰。 六个套路里它最不划算,原因见下一节——它恰好是最有教学价值的一个。

🧩 九、⭐ 倍数是规模的函数,不是常数

上表所有数字都只对 N = 200,000 成立。把 Top-K 这一条放到不同规模上看:

import numpy as np
import timeit

k = 10
for N in (200_000, 5_000_000):
    x = np.random.default_rng(0).random(N)
    t_sort = min(timeit.repeat(lambda: np.argsort(-x)[:k],         number=1, repeat=5))
    t_part = min(timeit.repeat(lambda: np.argpartition(-x, k)[:k], number=1, repeat=5))
    print(f"N = {N:>9,} : argsort {t_sort*1e3:7.2f} ms | "
          f"argpartition {t_part*1e3:6.2f} ms -> {t_sort/t_part:.1f}x")

算一算

N = 200,000 : argsort 8.91 ms | argpartition 2.66 ms -> 3.4x

N = 5,000,000 : argsort 603.00 ms | argpartition 56.09 ms -> 10.8x

(三次独立跑:N=200,000 时 3.4x / 3.2x / 2.8x;N=5,000,000 时 10.8x / 8.6x / 14.7x。倍数抖,但趋势不抖。)

⭐ 原因是复杂度不同:argsort 是 O(n log n),argpartition 是 O(n)。它们的比值本身就含一个 log n,所以规模涨 25 倍,优势从 3 倍涨到 9–15 倍。

💀 这条比六个漂亮的倍数都更值钱:任何「X 比 Y 快 N 倍」的说法,不写清楚 N 是多少就没有意义。你在 20 万行上量出的 3 倍,上线跑 500 万行时是 10 倍;反过来,你在 20 万行上量出的 100 倍,缩到 100 行时可能是 0.5 倍(更慢)。

🚦 十、什么时候不该改写

改写不是免费的。这四种情况请直接停手:

情况 为什么 怎么办
真正的顺序依赖 第 i 步要根据第 i−1 步的结果决定读哪个下标(比如并查集、A* 的开放列表),没有 ufunc 能表达 写循环。真嫌慢就换语言层,见 numba / C 扩展
中间体爆炸 03 章那个 (400,400,2) 的距离中间体是 2.4 MB,放大到 (3000,3000,16) 就是 1.1 GB —— N 翻 10 倍它翻 100 倍 分块(chunk)循环 + 块内向量化。⭐ 外层留一个循环是完全正常的写法
n 很小 每次 NumPy 调用有几微秒的固定开销,n=50 时纯 Python 反而赢 别改
可读性崩了 一行 np.flatnonzero(np.diff(np.signbit(np.where(...)))) 三个月后没人看得懂 ⭐ 拆成两三行并留注释,倍数几乎不变

⭐ 一条经验:先把循环改对,再测。本章每段代码都是「先 print 最大差 / 是否完全一致,再打印耗时」——顺序不能反。改快了但改错了,是最难查的一类 bug,因为它不报错。

04 / 完整解释

把一个套路带回自己的输入。

🔗 这一章连到哪里

相关的地方 为什么
06 · 索引的四种形态 ② 用的 bincount 是那一章「重复索引只写一次」的专用快速通道。先看懂 np.add.at 为什么存在,再回来用 bincount,否则你不知道自己躲开了什么坑
05 · 内存布局与 stride ④ 的 sliding_window_view 铺出 (199951, 50) 却不复制数据,为什么能这样,答案全在那一章的 stride 三元组。这里只用结论
03 · 广播的三条规则 「中间体爆炸」那一条的具体账(2.4 MB → 1.1 GB)在那一章算过。⭐ 决定要不要分块之前,先去那里学会估中间体大小
01 · 为什么写循环是错的 那一章讲为什么数组版更快(解释器开销、连续内存、SIMD),这一章只讲手怎么动。倍数看不懂就回去补那三层
ML 基础 · 附录 C · 手撕代码速查 那里的 conv2d 用 Ho×Wo 双重 Python 循环写前向——⭐ 那是故意的,白板题要的是「拆开给你看」。但你在自己项目里写卷积时,套路 ④ 是正确答案
Kaggle 竞赛方法论 · 01 · 数据策略与特征工程 套路 ② 和 ⑤(分组统计、分桶)就是特征工程里最高频的两个动作。那边讲造什么特征,这里讲怎么算得快
08 · 整数 dtype 的真相 ⚠️ 套路 ② 的组号是整数数组。组号很多时用 int16 存看起来省内存,但它会静默回绕——下一章的正题

✅ 检查点

  1. 判断一个循环该不该改写,本章给了哪三个问题?
  2. 「第 i 次要用第 i−1 次的结果」是不是就一定不能改写?举一个反例。
  3. 甲店用 axis=1 累计到第 2 天是多少?如果误把累加器设为 int8,结果是多少?
  4. 四组报表中只有组 0 和组 2 有记录。不写 minlength 时结果几格?如果出现组 4,只设 minlength=4 能挡住它吗?
  5. 对可安全取负的一维数组,np.argpartition(-x, k - 1)[:k] 拿到的前 k 个下标是有序的吗?要按值降序该怎么补?
  6. sliding_window_view(x, 50) 在 N=200,000 上展开成 (199951, 50),这一步占多少内存?为什么?
  7. 本章六个套路里,倍数最小的是哪个?大概多少?为什么它最小?
  8. Top-K 的倍数从 N=200,000 到 N=5,000,000 是怎么变的?原因是什么?
  9. np.flatnonzero(np.diff(y) != 0) 返回的下标,对应原数组 y 的第几个元素?
  10. 本章列了四种「不该改写」的情况,哪一种明确说了「外层留一个循环是正常的」?
👀 答案
  1. ① 有没有顺序依赖 ② 中间体有多大 ③ 一次跑几个元素(几十个就别改,本章倍数全部在 N = 200,000 上测)。
  2. 不一定。前缀和就是顺序依赖,但 np.cumsum 一行搞定。真正的判据是「这个顺序依赖有没有现成的 ufunc accumulate」——np.add.accumulate / np.maximum.accumulate / np.logical_and.accumulate 都算。没有对应函数(比如每步结果决定下一步读哪个下标)才必须写循环。
  3. 60 + 70 = 130。int8 的上限是 127,这一步按 256 回绕,得到 130 − 256 = −126。
  4. 最大组号是 2,默认只有 3 格,组 1 的计数为 0。组 4 出现后输出会扩成 5 格。minlength 只保证至少 4 格,验证组号范围需要另做检查。
  5. 无序。kth 从 0 开始;在 -x 上分区时,左侧值不大于分区点,对应原数组较大的元素。要有序就 idx[np.argsort(-x[idx])] 再对这 k 个排一次,k 小时几乎不花钱。
  6. 不占(0 额外内存)。实测 np.shares_memory(v, x) 是 True ——它没复制,只是给同一块内存换了套 stride 读法。「如果真复制」是 76.3 MiB,而 x 本身只有 1.5 MiB。为什么能这样见 05 章。
  7. ③ Top-K,只有 3.5–5.7x。因为 argsort 和 argpartition 都是 C 实现的数组操作,两边都没有 Python 循环开销,差的只是 O(n log n) 和 O(n) 这个算法复杂度;其余五个是「Python 循环 vs C 循环」,差的是一整层解释器开销。
  8. 从 3.4x 涨到 10.8x(三次跑:200,000 时 3.4/3.2/2.8x,5,000,000 时 10.8/8.6/14.7x)。因为两者比值里含一个 log n,规模涨 25 倍,优势就涨了一档。结论:倍数是规模的函数,不写清 N 的倍数没有意义。
  9. 对应 y 的第 i+1 个。np.diff(y) 比 y 短 1,d[i] 描述的是 y[i] 和 y[i+1] 之间的关系。差这个 1 是本套路唯一的高频错误。
  10. 中间体爆炸那一条:分块循环 + 块内向量化,外层留一个循环是完全正常的写法。

本节回顾

⚡ 走神救援

这一章只做一件事:给「拿到一个循环,手怎么动」列一张对照表。 动手前先过三个问题——有没有顺序依赖、中间体多大、一次跑几个元素(只有几十个就别改)。

⭐ 第一个问题最容易判错:「要用上一次的结果」不等于「必须写循环」——前缀和就是顺序依赖,而一个 cumsum 就够。真正的判据是这个依赖有没有现成的 ufunc accumulate。

六个套路里最值得记的四条:分组求和用 bincount 最猛(循环版每轮都在做哈希、装箱、字典查找),⚠️ 固定报表宽度时用 minlength 补末尾空组,并另查组号上界;Top-K 用 argpartition 而不是全排序,⚠️ 结果无序;滑窗用 sliding_window_view——⭐ 它展开成一个大得多的形状却和原数组共享内存,「如果真复制」会是几十倍的内存;分桶用 searchsorted,⚠️ side 决定等值归左还是归右。

⭐⭐ 全章最该带走的一条不是任何一个函数,是「倍数是规模的函数」:同一个改写在小规模上只快几倍、在大规模上快十几倍,因为比值里含一个 log。所以「X 比 Y 快 N 倍」不写清 N 就没有意义。 ⚠️ 同理,同一台笔记本三次独立跑,同一个倍数能差近一倍——那是热降频不是测错,看量级不看绝对值。

最后四种情况直接停手不要改:真正的顺序依赖、中间体爆炸(⭐ 这时外层留一个循环是正常写法)、n 很小(每次调用有固定开销)、可读性崩了。

⭐ 顺序永远是先改对再测——本章每段代码都先打印「最大差 / 是否完全一致」再打印耗时。改快了但改错了不报错,是最难查的一类 bug。

下一节 👉 08-整数dtype的真相.md

打卡记录保存在你的浏览器里,首页能看到总进度

改写成整块运算后,数值却可能悄悄回绕。下一次先检查数组的 dtype。