
轮式筛法通过跳过已知合数倍数来缩小搜索空间,但实验表明:使用模210轮子(48个余数)相比模30轮子(8个余数)几乎不提升性能,根本原因在于核心耗时操作(批量标记合数)未被优化,而轮子仅加速了“找素数”这一次要环节。
轮式筛法通过跳过已知合数倍数来缩小搜索空间,但实验表明:使用模210轮子(48个余数)相比模30轮子(8个余数)几乎不提升性能,根本原因在于核心耗时操作(批量标记合数)未被优化,而轮子仅加速了“找素数”这一次要环节。
在素数筛选实践中,轮式筛法(Wheel Factorization)是一种经典的空间压缩策略:它利用前 $k$ 个素数的乘积 $M = p_1 p_2 \cdots p_k$ 构造“轮子”,只在与 $M$ 互质的剩余类中检查候选数。例如:
- 模 $30 = 2 \times 3 \times 5$ 的轮子保留 $8$ 个余数:
[1, 7, 11, 13, 17, 19, 23, 29],覆盖约 $26.7\%$ 的整数; - 模 $210 = 2 \times 3 \times 5 \times 7$ 的轮子保留 $48$ 个余数,覆盖率降至约 $22.9\%$,理论搜索空间减少约 $14\%$。
直觉上,更小的候选集应带来线性加速。但你的基准测试(如 n = 4\,194\,304 时 prime_wheel_sieve4 反而慢 $5.5\%$)揭示了一个关键事实:算法的运行时间并不由“检查多少候选数”主导,而由“对每个发现的素数执行多少内存写操作”决定。
? 性能瓶颈定位:primes[...] = False 是真正的热点
观察两版代码的核心循环:
if primes[k]:
primes[k**2 :: 2 * k] = False # ← 这行占总耗时 >90%该语句对每个素数 $k \leq \sqrt{n}$ 执行一次切片赋值,其开销取决于:
- 起始位置 $k^2$,
- 步长 $2k$,
- 目标数组长度 $n$,
- 与轮子大小完全无关。
无论你用模30还是模210轮子,只要 $k$ 是素数,这行代码的执行次数(即 $\pi(\sqrt{n}) \sim \frac{2\sqrt{n}}{\ln n}$)、每次迭代的内存访问量、缓存行污染程度都基本一致。Numba 编译后,该操作底层调用高度优化的向量化内存写入(如 memset 或 SIMD store),其吞吐量由硬件带宽和缓存局部性决定,而非外层循环的步进逻辑。
相比之下,轮子优化仅影响“如何递增 $k$”这一轻量级操作:
- 模30轮子:每轮8次加法 + 1次取模(
i = (i+1) % 8); - 模210轮子:每轮48次加法 + 1次取模(
i = (i+1) % 48)。
虽然模运算次数相同,但轮子越大,遍历到每个素数所需的迭代次数越少(因跳过更多合数),看似有利。然而:
- 素数密度在 $[7, \sqrt{n}]$ 区间本就极低(例如 $\sqrt{4\,194\,304} \approx 2048$,其间仅约 $309$ 个素数);
- 轮子优化节省的“非素数判断”次数,在总循环次数中占比微乎其微(
- 更大的轮子数组(48元 vs 8元)反而可能轻微增加指令缓存压力或破坏 CPU 分支预测。
✅ 验证:剥离轮子影响的对比实验
你后续用 prime_wheel_sieve3 和 prime_wheel_sieve4_1 控制变量的测试结果(如 n=524288 时 1.45ms vs 1.42ms)进一步证实:轮子尺寸对性能的影响远小于测量噪声。微弱的正向波动(-2%)源于:
- 更大的轮子略微改善了 $k$ 的分布均匀性,使
primes[k]的缓存命中率小幅提升; - Numba 对不同长度常量数组的内联/向量化策略存在细微差异。
但这绝非理论预期的 $14\%$ 加速——因为那假设“找素数”是瓶颈,而实际瓶颈是不可绕过的合数标记阶段。
? 实用建议:何时以及如何有效使用轮子?
| 场景 | 是否推荐轮子 | 原因 |
|---|---|---|
| 教学/小规模筛($n | ❌ 不必要 | 简单埃氏筛足够快;轮子增加代码复杂度,无实际收益 |
| 大范围筛($n > 10^7$),内存受限 | ✅ 推荐模30或模210 | 显著降低内存占用(布尔数组稀疏化),利于缓存;但需配合分段筛(Segmented Sieve)避免一次性分配大数组 |
| 追求极致性能(如密码学预计算) | ⚠️ 优先优化合数标记 | 改用位压缩(bitarray)、并行化 primes[...]=False、或切换至线性筛(欧拉筛)消除冗余标记 |
? 关键洞见:轮式筛法本质是空间换时间的启发式剪枝,而非复杂度阶的突破。它无法改变算法主导项 $O(n \log \log n)$ 的渐近行为,仅在常数因子上做有限优化。真正的性能跃迁来自重构数据访问模式(如分段筛减少缓存失效)或更换算法范式(如线性筛将标记复杂度降至 $O(n)$)。
? 总结
- 误区纠正:“缩小搜索空间”不等于“加速算法”——必须识别并优化真正的性能瓶颈(此处为批量内存写入)。
- 数据说话:你的实测结果完全符合理论预期:轮子优化仅影响低开销控制流,对整体耗时不构成显著影响。
- 工程启示:在算法优化中,永远先做性能剖析(profiling),再基于热点而非直觉做改进。否则,就像给汽车换更轻的后视镜却忽视发动机调校——细节再精致,也无法提升百公里加速成绩。
轮子仍是优雅的数学构造,但在工程实现中,它更像一个精巧的仪表盘,而非引擎本身。


















