讲师中心 微信公众号

工具推荐

视频效率加速
updream

一键生成高质量推广成片

Seko
Seko

AI短剧一键生成成片

剧云
剧云

中文短剧剧本制作平台

SoundView
SoundView

字幕擦除翻译、配音口型同步

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

云静小哥_8802

云静小哥_8802

发布时间:2026-11-21 14:35:03

|

256人浏览过

|

来源于php中文网

原创

为什么更大的轮子(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 <= lim:
    if primes[k]:                            # 检查:轮子在此处起效 → 减少判断次数
        primes[k**2 :: 2*k] = False         # 标记:主导耗时操作 → 占比 >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 的所有质数)是固定的,标记工作量完全不变。

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

    • 更大的轮子(如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

热门AI工具

更多
讯飞智作

讯飞智作是一款AI视频创作工具,AI文本配音工具,数字人课程、营销视频制作。

WorkBuddy

一款AI办公效率工具,主要用于腾讯云推出的AI原生桌面智能体工作台,适合需要提升相关任务效率的用户。

超级麦吉

一款通过数字员工协作完成调研、数据分析与文档制作的AI办公平台。

豆包大模型

豆包大模型是一款由字节跳动推出的企业级大语言模型服务平台。

DeepSeek

DeepSeek是一款面向对话、写作、编程和推理场景的AI大模型工具。

SoundView
SoundView Hot

SoundView是一款面向跨境电商的视频翻译、配音和本地化 AI 创作平台。

立刻MV
立刻MV Hot

立刻MV是一款AI文本写作工具,AI 音乐视频(MV)创作工具。

音述AI
音述AI Hot

一款AI音频处理工具,主要用于音述AI是一个以“用声音述说故事”为核心的 AI 音乐创作与声音分享社区,适合需要提升相关任务效率的用户。

创客贴AI

创客贴AI是一款AI图像与设计工具,AI辅助的智能在线设计工具。

相关专题

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

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

1971

2023.07.20

python能做什么
python能做什么

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

5644

2023.07.25

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

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

1909

2023.07.31

python教程
python教程

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

34577

2023.08.03

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

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

4027

2023.08.04

python eval
python eval

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

4047

2023.08.04

scratch和python区别
scratch和python区别

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

1303

2023.08.11

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

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

636

2023.08.10

Navicat创建数据库教程
Navicat创建数据库教程

本专题整理Navicat创建数据库相关教程,介绍新建前的准备、基础设置和创建后的检查方法。内容兼顾入门学习及实际使用需求,帮助用户了解不同数据库类型下的操作差异,为后续建表、保存数据和日常管理提供参考。

0

2026.11.20

热门下载

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

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号
PHP中文网订阅号
每天精选资源文章推送

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn