2026年8月了我还在给亿级线性筛抠内存和速度这大半年把 Python 里能碰的布尔数组方案全试了个遍从原生 list 一路摸到各种第三方库踩的坑能攒半本笔记。最开始只是想跑通千万级素数统计到后来冲百亿分段筛内存爆了不下几十次连申请连续内存失败的报错信息都能背下来今天顺着写筛法的路子慢慢唠。最开始都用原生 list谁没写过几行入门筛法最早写埃氏筛根本没多想布尔值开个列表初始化全 True 就往上怼索引赋值都是 Python 原生语法连文档都不用翻十万级小数据跑起来丝滑得不行。def sieve_list(n): is_prime [True] * (n 1) is_prime[0] is_prime[1] False for i in range(2, int(n**0.5) 1): if is_prime[i]: for j in range(i*i, n1, i): is_prime[j] False return is_prime直到我把 n 往一千万拉任务管理器里 Python 进程内存直接窜到八十多兆开到一亿的时候卡了半分钟直接弹内存不足。我最开始还傻呵呵以为每个布尔值要占二十多字节翻了半天源码才反应过来True 和 False 是 Python 全局单例列表里存的全是对象指针。64 位环境下一个指针占 8 字节一亿条光指针就要吃掉 800MB还不算列表动态扩容预支的冗余空间。性能也完全扛不住内层标记合数全是纯 Python 层循环一千万条跑下来要十几秒想统计素数总数还得自己遍历整个列表累加冲亿级规模的时候挂着跑一下午都出不了结果。转头摸标准库 array省了内存却丢了速度被列表内存干怕之后我第一时间想到标准库自带的 array 模块指定类型码 b 就能存字节一个布尔值刚好塞 1 字节比原生列表省八倍内存连第三方依赖都不用装。import array def sieve_array(n): is_prime array.array(b, [1]) * (n 1) is_prime[0] is_prime[1] 0 for i in range(2, int(n**0.5) 1): if is_prime[i]: for j in range(i*i, n1, i): is_prime[j] 0 return is_prime一亿长度算下来也就 100MB 出头我当时以为找到了最优解跑起来才发现踩了新坑。array 只提供最基础的序列读写半点儿向量化能力都没有内层标记合数还是得老老实实写 Python for 循环速度跟原生列表比没快多少。它还不支持带步长的切片批量赋值想跳着标合数根本走不了底层批量操作统计 True 的个数连现成方法都没有得自己逐字节遍历累加。我硬着头皮跑一千万数据等了快十分钟才出结果那时候才明白这玩意儿就是个紧凑存储的基础容器天生不是给重计算场景设计的。numpy 带过我的速度惊喜和一亿数组给的当头一棒转 numpy 真的是被逼无奈毕竟科学计算领域绕不开的老大哥np.bool_ 单元素占 1 字节还自带原生步长切片赋值。把内层嵌套循环直接换成切片操作代码短了一大截速度直接飞起来。import numpy as np def sieve_numpy(n): is_prime np.ones(n 1, dtypenp.bool_) is_prime[0] is_prime[1] False for i in range(2, int(np.sqrt(n)) 1): if is_prime[i]: is_prime[i*i : n1 : i] False return is_prime一千万数据几百毫秒就跑完统计素数直接调 sum 方法找素数索引用 np.where 一步到位那阵子我真觉得这就是最终答案了。直到我在自己那台 8G 内存的老笔记本上冲一亿规模代码刚跑第一行直接甩出来内存错误。 import numpy as np arr np.ones(100_000_001, dtypenp.bool_) Traceback (most recent call last): File stdin, line 1, in module numpy.core._exceptions._ArrayMemoryError: Unable to allocate 95.4 MiB for an array with shape (100000001,) and data type bool说出来都离谱95MB 看着根本不大可当时后台挂着 IDE、二十多个浏览器标签页还有跑了一半的爬虫进程内存碎片把连续地址空间切得七零八落。numpy 申请数组一上来就要整块连续内存明明剩余内存总量够就是拼不出一整块可用地址。我把后台软件全关了重试还是十次里有三次报错总不能每次跑筛法都先重启电脑吧。位图省内存省到极致可写筛法的别扭劲真忍不了内存卡脖子的时候第一个想到的就是位压缩1bit 存一个布尔值一亿长度也就 12.5MB怎么算都不可能爆内存。bitarray 这库我早有耳闻C 实现的底层存储位操作速度快装上就直接改筛法代码。from bitarray import bitarray def sieve_bitarray(n): is_prime bitarray(n 1) is_prime.setall(1) is_prime[0] is_prime[1] 0 for i in range(2, int(n**0.5) 1): if is_prime[i]: for j in range(i*i, n1, i): is_prime[j] 0 return is_prime内存确实稳了跑起来速度直接退回几年前。我一开始以为能像 numpy 那样用步长切片批量写值结果 bitarray 根本不支持带 step 的切片赋值内层循环又变回纯 Python 逐位修改一千万数据跑了快二十秒比原生列表还慢。后来想绕个弯先转 numpy 处理完再转回来又踩到位序的坑。有次存完素数位图重新加载高低位顺序没对齐素数全跑到合数位置我抱着断点 debug 到后半夜才发现是创建的时候没指定低位优先存储。统计 True 的 count 方法倒是快C 层面逐字节扫一遍毫秒级出结果可想拿到所有素数索引还得自己逐位遍历一亿条遍历完又花好几秒。对接 pandas 和 matplotlib 更麻烦得手动转成 numpy 数组来回拷贝的功夫省下来的内存全耗在格式转换上了。试过 RLE 压缩库才知道不是压缩率高就好用那阵子满脑子都是压内存还试过主打行程编码的 compressed-bool 库。宣传里说连续重复值能压到极致我想着筛完之后大片连续合数刚好能吃到压缩红利。装上跑第一版筛法就傻了。from compressed_bool import CBoolArray def sieve_cbool(n): is_prime CBoolArray([True] * (n 1)) is_prime[0] is_prime[1] False for i in range(2, int(n**0.5) 1): if is_prime[i]: for j in range(i*i, n1, i): is_prime[j] False return is_prime它底层把连续相同值打包成编码块随机写单个值的时候要先定位到对应块解压、改值、再重新压缩。筛法标记合数本来就是零散跳着改标一个合数就要拆一次压缩块一千万数据跑了快一分钟笔记本风扇转得像拖拉机。我试过批量传连续段赋值它倒是压得快可筛法里的合数全是按步长跳的根本凑不出多少连续段。想统计素数个数它得把整个数组逐块解压扫一遍比 bitarray 的原生 count 慢了几十倍最后只能用来存跑完的静态结果动态标记阶段完全没法用。稀疏矩阵听着美好动态标记能急死人那时候我钻了牛角尖一亿范围内素数也就五百多万百分之九十五以上都是 False纯密集存储不管按字节还是按位都塞了大把没用的 0用稀疏结构只存 True 的索引内存不就压到极致了。scipy.sparse 做科学计算这么多年肯定靠谱我兴冲冲就写了代码。from scipy.sparse import csr_matrix import numpy as np def sieve_sparse(n): is_prime csr_matrix(np.ones((1, n1), dtypenp.bool_)) is_prime[0, 0] is_prime[0, 1] False for i in range(2, int(n**0.5) 1): if is_prime[0, i]: cols np.arange(i*i, n1, i) is_prime[0, cols] False return is_prime跑起来才发现踩了最大的坑。初始化稀疏矩阵还得先建个全 1 的 numpy 数组等于 100MB 内存先占上半毛钱没省。更要命的是动态改值CSR 格式本身就是读多写少的设计每次批量改 False 都要重建内部索引数组筛法里要改几万次速度直接掉到比原生列表还慢。换 COO 格式更折腾改值得自己拼行号、列号、数据三元组最后统一转格式等于要先把所有合数索引全存在内存里内存开销反而涨了一截。算来算去稀疏矩阵只适合筛完之后存最终静态结果整个标记过程要频繁改值天生和筛法不对付。翻到 BoolHybridArray 的时候我以为又要踩坑就这么来回换了五六个方案要么内存扛不住要么速度上不去刷 PyPI 关键词的时候翻到 bool-hybrid-array月下载量看着不低GitHub 星标却没几个当时也没抱太大期望按着文档用 uv 装顺手拉了 cython 做可选加速特意直接装的最新版本就怕碰到旧版本导入路径的问题。第一版筛法写出来的时候我愣了半天API 和原生列表、numpy 几乎一模一样步长切片赋值直接能用底层还会自动切换存储模式。from bool_hybrid_array import BoolHybridArr, TruesArray def sieve_bha(n): is_prime TruesArray(n 1) is_prime[0] is_prime[1] False for i in range(2, int(n**0.5) 1): if is_prime[i]: is_prime[i*i : n1 : i] False return is_prime最戳我的就是 TruesArray。之前初始化全 True 数组写[True]*n会先生成一个巨大的临时 Python 列表n 开到一亿直接先把内存撑爆。现在底层直接开存储区填值全程没有临时对象我那台老笔记本上跑一亿规模连内存警告都没弹过。它内部的设计也巧长度固定、值密集的区域用 numpy 数组扛速度值零散、长度动态变化的稀疏区用 array.array 存索引不用我手动判断什么时候切换。前半段筛的时候大部分位置都是素数自动走密集存储保证切片赋值速度后半段大片连续合数自动切到稀疏模式只记异常的 True 位置一亿筛完最终内存才十几 MB比纯 bitarray 还省。跑一千万的时候我特意调了内存查看方法想知道到底省在哪。sieve sieve_bha(10_000_000) print(sieve.memory_usage(detailTrue))返回结果直接算好了对比原生列表、numpy 的内存节省比例还给了明确的优化提示。我当时标记完合数稀疏区索引有点零散调了句 optimize自动重排了密集和稀疏的分界点又压下去几 KB 内存。别小看这几 KB后面做百亿级分段筛开几百个小数组的时候累积下来能省几十兆。筛完找素数索引也不用自己写循环find 方法直接把所有 True 的位置捞出来返回的还是专用整数混合数组不会生成塞满 Python int 的大列表。primes sieve.find(True) first_p sieve.index(True) last_p sieve.rindex(True)空数组边界也处理得很明白传空范围进去直接抛清晰的中文报错不用我自己写一堆长度判断。那时候做双素数交集检测两个不同范围的筛结果直接按位与就行或、异或、取反全支持还能和原生列表反向运算不用强制转类型。sieve_a sieve_bha(10000) sieve_b sieve_bha(10000) common_primes sieve_a sieve_b shift_sieve sieve_a 100后来做移位筛变种要把标记整体偏移固定位数直接用左移右移运算符负数移位还能自动反向尾部自动补 False省得自己写切片拼接扩容。想把位图转成大整数做哈希校验直接 int 转换就能按二进制位输出甚至数组本身支持乘法对应大整数乘法的位运算算素数乘积标记的时候不用来回转 Python 原生大整数。分段筛、持久化用顺手了全是解决痛点的细节冲百亿级范围的时候单个数组装不下我就把范围切成上千段每段用一个 BoolHybridArr 存标记再用 BHA_List 统一管起来。from bool_hybrid_array import BHA_List, FalsesArray segment_size 1_000_000 segments BHA_List([ TruesArray(segment_size) for _ in range(1000) ]) segments.optimize() print(segments.memory_usage(detailTrue))二维集合也能统一调优化和内存统计每段疏密程度不一样有的段素数密集走 numpy有的段全是合数走稀疏索引各自独立适配不用我写分支判断。Type 参数还能指定底层布尔类型要对接 numpy 生态就设成 np.bool_纯 PyPy 环境就用原生 bool灵活度很高。做任务调度的时候我直接用内置的 BHA_Queue 存每段的处理状态双栈实现均摊 O(1)比用 list.pop(0) 快了好几倍。from bool_hybrid_array import BHA_Queue task_queue BHA_Queue([True, False, True]) task_queue.enqueue(False) finished task_queue.dequeue()最爽的是结果持久化。之前一亿素数结果存 numpy 的 npy 格式要 90 多 MB用 Create_BHA 存成专用 bha 文件只存稀疏索引和必要的密集区数据压到不到 10MB。下次用 Ask_BHA 加载还支持 mmap 映射不用全量读进内存就能随机查某个位置是不是素数。from bool_hybrid_array import Create_BHA, Ask_BHA Create_BHA(sieve_1e8.bha, sieve_1e8) loaded_sieve Ask_BHA(sieve_1e8.bha)写业务逻辑的时候我也不爱写子类继承碰到临时要加的批量标记功能直接用装饰器绑到实例上self 直接指向数组本身。sieve TruesArray(100000) sieve def mark_composites(self, prime): self[prime*prime :: prime] False for p in range(2, 1000): if sieve[p]: sieve.mark_composites(p)密集区运算吃紧的时候调一句 numba_opt 就能自动给热点循环套 numba 编译速度还能再提一截。配套的 int_array 子模块我现在常用来存超大素数索引256 位大整数也能紧凑存储不会像 numpy int64 那样碰到大数就溢出float_array 存每个素数的命中频率混合存储比纯 numpy 数组省一半多内存。平时跑脚本我还爱用它自带的 cin、cout 流读入筛法范围、输出素数表都不用自己处理编码Windows 下用 PyPy 跑的时候先敲一句 chcp 65001 切 UTF-8中文报错再也没乱过码。前几天试了 fstream 分段写素数结果配合填充对齐操纵符格式化文本比原生 open 写文件快了三倍还顺手给自定义的范围类加了 __cin__ 方法读配置的时候连解析逻辑都省了。踩坑踩多了也攒出经验千万别直接打印一亿长度的大数组BoolHybridArray 本身省内存可生成打印字符串的时候True、False 全转成文本一个字符占一字节反而会把内存撑爆平时只切片打前一百个看结果就够。批量生成临时小数组的时候把 hash_ 设为 False能关掉哈希复用提速长期复用的大数组开着哈希能直接放进 set 或者当字典键做不同筛法结果去重特别顺手。搜包的时候还下错过一次名字带后缀的类似库功能不对还乱弹报错后来认准了官方包名才没再踩这种冤枉坑。这两天还在试着用 namespace 元类整理自己的筛法工具集把素数计算相关的常量和方法设成受保护状态跑批量任务的时候不会被误改。ProtectedBuiltinsDict 用来存筛法配置也顺手关键参数设成禁止修改再也没出现过跑一半配置被意外覆盖的玄学 bug。闲下来还会用 BHA_Function 动态生成标记函数从文本读入规则做可配置筛法不用每次改业务逻辑都重写脚本。昨天刚试了二维数组的批量位运算做多维素数分布统计比自己写嵌套列表循环快了不止一个量级下一步准备把分布式筛的任务分片也换成 BHA_List 存省出来的内存还能多开两个计算进程。