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

云静小哥_8802

云静小哥_8802

2026-11-21

256人浏览

原创

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

轮式筛法通过跳过已知合数倍数来缩小搜索空间,但实验表明增大轮子(如从30到210)几乎不提升性能;根本原因在于:算法耗时主体是标记合数的内存写操作,而轮子仅优化了“找质数”的次要环节。

轮式筛法通过跳过已知合数倍数来缩小搜索空间,但实验表明增大轮子(如从30到210)几乎不提升性能;根本原因在于:算法耗时主体是标记合数的内存写操作,而轮子仅优化了“找质数”的次要环节。

在素数筛法的工程实践中,一个常见直觉是:“轮子越大,跳过的合数越多,检查的候选数越少,速度理应越快”。你正确推导出:基于模30的轮子只需检查8/30 ≈ 26.7%的数,而模210轮子进一步压缩至48/210 ≈ 22.9%,理论搜索空间缩减约14%。然而实测结果却令人困惑——prime_wheel_sieve4_1(210轮)与prime_wheel_sieve3(30轮)运行时间几乎持平,甚至波动在±1%以内。这并非代码缺陷或测量误差,而是触及了算法性能分析的核心原则:优化必须作用于真正的时间支配项(time-dominating operation)。

我们来拆解轮式筛法的执行开销:

# 关键操作分解(以 prime_wheel_sieve4_1 为例)
primes = np.ones(n + 1, dtype=np.uint8)      # O(n) 初始化,仅一次
primes[:2] = False                           # O(1)
for square, step in ((4,2), (9,6), (25,10), (49,14)):
    primes[square::step] = False             # 四次切片赋值,O(n/2 + n/6 + n/10 + n/14) ≈ O(n)
k = 11; lim = int(sqrt(n))
while k 95%
    k += wheel[i]; i = (i+1) % 48            # 轮子步进:极轻量计算
  • ✅ 轮子优化的是 if primes[k]: 这一判断路径:它减少了需进入内层标记逻辑的 k 的数量(例如,210轮下检查约22.9%的数,30轮下为26.7%)。但该判断本身是单次内存读取(primes[k]),成本极低(纳秒级)。

  • ❌ 轮子完全未改变主导开销:`primes[k2 :: 2*k] = False**。对每个质数k ≤ √n,此操作需执行约n/(2k)次内存写入。其总成本为: [ sum_{substack{k ext{ prime} \ k leq sqrt{n}}} rac{n}{2k} pprox rac{n}{2} cdot sum_{k leq sqrt{n}} rac{1}{k} sim rac{n}{2} cdot ln ln n ] 这一求和项由质数分布决定,**与轮子大小无关**——无论你用30轮还是210轮,只要k是质数,就必须对它的所有 ≥k² 的倍数做标记。轮子只是帮你更快地 *到达*k,但k` 的集合(即 ≤√n 的所有质数)是固定的,标记工作量完全不变。

  • ⚠️ 轮子反而引入微小开销:

    锦鲤求职
    锦鲤求职

    一款面向校招和实习求职者的AI岗位筛选与网申助手。

    下载
    • 更大的轮子(如48元素数组)导致 wheel[i] 查表访问的缓存局部性略差;
    • i = (i+1) % 48 比 % 8 多一次除法(尽管Numba可能优化为乘法逆元,但仍非零成本);
    • 预处理的初始质数更多(需手动筛掉2,3,5,7而非仅2,3,5),增加常数项。

? 类比理解:想象一支工程队修建一条100公里公路。轮子优化相当于改进了勘测员寻找“适合打地基的位置”的效率——从每公里勘测15个点减少到10个点。但修路耗时99%花在混凝土浇筑和压实上,而这完全取决于公路总长和地质条件,与勘测点密度无关。再快的勘测,也无法让浇筑变快。

因此,追求更大轮子是典型的“优化错位”(premature optimization)。若真要提升筛法性能,应聚焦:

  • 使用更高效的数据结构(如bitarray替代np.ndarray[uint8],节省7/8内存带宽);
  • 并行化标记阶段(primes[k**2 :: 2*k] 可分段并行);
  • 采用分段筛(Segmented Sieve)突破内存限制,提升缓存命中率;
  • 对于超大 n,切换至线性筛法(如欧拉筛),将时间复杂度从 O(n log log n) 降至 O(n)。

轮子的价值不在速度,而在概念清晰性与可扩展性:它将“哪些数可能为质数”这一数论结构(即与基础模数互质的剩余类)显式编码,是连接初等数论与高效算法的优雅桥梁——只是这座桥,不负责承载主要车流。

相关文章

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

该软件包括了市面上所有手机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

34577

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人学习