为什么更大的轮子(wheel)并未加速轮式筛法?——揭秘素数筛选中的性能瓶颈

小晨小哥_7526

小晨小哥_7526

2026-11-21

365人浏览

原创

为什么更大的轮子(wheel)并未加速轮式筛法?——揭秘素数筛选中的性能瓶颈

轮式筛法通过跳过已知合数倍数来缩小搜索空间,但实验表明:使用模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$”这一轻量级操作:

ClawUsage Windows Hardlock
ClawUsage Windows Hardlock

一款AI工具,主要用于通过聊天(Telegram / 飞书)执行本地 `clawusage` 监控命令。当用户输入 `/clawusage ...`,或提出“查看 Codex 用量”、“开启/关闭自动…”等请求时触发使用,适合需要提升相关任务效率的用户。

下载
  • 模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),再基于热点而非直觉做改进。否则,就像给汽车换更轻的后视镜却忽视发动机调校——细节再精致,也无法提升百公里加速成绩。

轮子仍是优雅的数学构造,但在工程实现中,它更像一个精巧的仪表盘,而非引擎本身。

相关文章

数码产品性能查询
数码产品性能查询

该软件包括了市面上所有手机CPU,手机跑分情况,电脑CPU,电脑产品信息等等,方便需要大家查阅数码产品最新情况,了解产品特性,能够进行对比选择最具性价比的商品。

下载

相关标签:

性能瓶颈

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
python打包成可执行文件
python打包成可执行文件

本专题为大家带来python打包成可执行文件相关的文章,大家可以免费的下载体验。

2023.07.20

1971

4

python能做什么
python能做什么

python能做的有:可用于开发基于控制台的应用程序、多媒体部分开发、用于开发基于Web的应用程序、使用python处理数据、系统编程等等。本专题为大家提供python相关的各种文章、以及下载和课程。

2023.07.25

5644

7

format在python中的用法
format在python中的用法

Python中的format是一种字符串格式化方法,用于将变量或值插入到字符串中的占位符位置。通过format方法,我们可以动态地构建字符串,使其包含不同值。php中文网给大家带来了相关的教程以及文章,欢迎大家前来阅读学习。

2023.07.31

1909

3

python教程
python教程

Python已成为一门网红语言,即使是在非编程开发者当中,也掀起了一股学习的热潮。本专题为大家带来python教程的相关文章,大家可以免费体验学习。

2023.08.03

34557

23

python环境变量的配置
python环境变量的配置

Python是一种流行的编程语言,被广泛用于软件开发、数据分析和科学计算等领域。在安装Python之后,我们需要配置环境变量,以便在任何位置都能够访问Python的可执行文件。php中文网给大家带来了相关的教程以及文章,欢迎大家前来学习阅读。

2023.08.04

4027

5

python eval
python eval

eval函数是Python中一个非常强大的函数,它可以将字符串作为Python代码进行执行,实现动态编程的效果。然而,由于其潜在的安全风险和性能问题,需要谨慎使用。php中文网给大家带来了相关的教程以及文章,欢迎大家前来学习阅读。

2023.08.04

4047

5

scratch和python区别
scratch和python区别

scratch和python的区别:1、scratch是一种专为初学者设计的图形化编程语言,python是一种文本编程语言;2、scratch使用的是基于积木的编程语法,python采用更加传统的文本编程语法等等。本专题为大家提供scratch和python相关的文章、下载、课程内容,供大家免费下载体验。

2023.08.11

1303

5

python合并两个列表
python合并两个列表

Python是一种强大的编程语言,具有许多方便的功能和工具。在Python中,有多种方法可以合并两个列表。php中文网给大家带来了相关的教程以及文章,欢迎大家前来学习阅读。

2023.08.10

636

4

python是前端还是后端
python是前端还是后端

Python属于前端也属于后端,其灵活性和丰富的生态系统使得开发人员能够在不同的领域中灵活运用。本专题为大家提供python相关的文章、下载、课程内容,供大家免费下载体验。

2023.08.11

3143

5

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
Swoole手册
Swoole手册

共0课时 | 0人学习