Python筛10亿素数内存炸了？从埃氏筛到混合布尔数组的踩坑实录

「部分情节为虚构演绎，仅供参考」

事情是这样的。那天我在刷算法题，遇到一道经典题：筛出10亿以内的所有素数。埃氏筛（Sieve of Eratosthenes）嘛，算法课第一节就教过。开一个布尔数组，初始全是True，然后从2开始，把每个素数的倍数全部标记为False。最后剩下True的就是素数。代码写出来就三行：

defsieve(n):is_prime=[True]*(n+1)is_prime[0]=is_prime[1]=Falseforiinrange(2,int(n**0.5)+1):ifis_prime[i]:forjinrange(i*i,n+1,i):is_prime[j]=Falsereturn[iforiinrange(2,n+1)ifis_prime[i]]

跑sieve(10_000_000)（一千万），没问题，几秒钟出结果。然后我手贱，把参数改成了sieve(1_000_000_000)（十亿）。那一刻，我的16GB内存笔记本直接卡死，风扇狂转，最后OOM Killer把Python进程杀了。「筛素数」变成了「筛内存」——不是筛掉合数，是把我内存筛没了。

为什么10亿布尔值能把内存撑爆

先算笔账。Python的list[bool]存的不是布尔值本身，而是指向PyObject的指针。64位系统上每个指针8字节，10亿个元素就是80亿字节，约7.5GB。但这还没完。True和False虽然是全局单例，但list里存的是8字节指针。7.5GB只是指针的开销，还没算list对象本身的开销、内存碎片、以及Python解释器本身占的内存。16GB的机器，系统+浏览器+IDE先占掉一半，剩下8GB给Python，7.5GB的数组一塞进去，直接爆。

方案一：bytearray，1字节/元素

Python内置的bytearray每个元素占1字节，10亿个就是10亿字节，约930MB。内存降了一个数量级，但还是接近1GB。

is_prime=bytearray(b'\x01')*(n+1)

930MB对于16GB的机器来说勉强能跑，但留给其他程序的空间就不多了。而且如果我想筛到100亿呢？9.3GB，又爆了。

方案二：numpy.ndarray，同样1字节/元素

importnumpyasnp is_prime=np.ones(n+1,dtype=np.bool_)

numpy的bool_也是1字节/元素，10亿个约930MB。好处是向量化操作快，筛素数的内层循环可以用切片赋值代替Python for循环，速度起飞：

is_prime[i*i:n+1:i]=False

但内存问题没解决——930MB就是930MB，numpy也变不出更少的字节来。而且numpy数组是定长的，如果你想动态扩展（比如先筛到10亿，发现不够要追加到20亿），np.append每次全量拷贝，直接卡死。

方案三：自己手搓位运算，1比特/元素

既然1字节/元素还是太大，那就1比特/元素呗。用int当位图，或者用array('Q')存64位整数，自己写位运算：

defset_bit(arr,i):arr[i>>6]|=(1<<(i&63))defget_bit(arr,i):return(arr[i>>6]>>(i&63))&1

10亿个布尔值压成1比特，只要约116MB。听起来很美对吧？但写起来极其痛苦：

• 位运算容易写错，>>和&的优先级能坑你半天；
• 边界处理：最后一个字可能不满64位，要掩码；
• 内层循环的切片赋值没了，得自己写循环遍历每个倍数的位，速度反而慢了；
• 代码可读性极差，三天后你自己都看不懂。

我搓了一下午，跑出来结果对了，但速度比numpy慢了5倍。内存是省了，时间又炸了。

方案四：bitarray库，1比特/元素

frombitarrayimportbitarray is_prime=bitarray(n+1)is_prime.setall(1)

10亿个元素约116MB，比numpy省8倍。API也比自己手搓位运算友好。但问题是：它不管你的数据分布，永远1比特/元素。素数在小范围内密度高（1到100有25个素数，密度25%），但在大范围里密度极低（10亿附近素数密度约4%）。也就是说，大部分位置都是False（合数），但bitarray依然老老实实为每个合数分配1比特。96%的空间在存False，纯浪费。

小结：各方案内存对比

从7.5GB到116MB，内存确实在降，但始终有一道坎：不管数据多稀疏，都得为每个元素分配固定空间。

破局思路：为什么不能「看菜下饭」

内存墙：省内存的真正意义

你可能觉得省内存就是「省点硬盘空间」。不是的。计算机的存储是分层的：寄存器 → L1缓存 → L2缓存 → L3缓存 → 主存 → 磁盘。每往下一层，速度慢100倍甚至100万倍。当你的数据放不进CPU缓存（L3一般几十MB），CPU就不得不频繁去主存取数据，这就是内存墙（Memory Wall）。数据量再大，主存放不下了就用Swap（磁盘），速度直接掉到每秒几MB。所以省内存的本质不是「省」，而是让数据离CPU更近。116MB的位数组能放进L3缓存，速度比930MB的numpy数组快——不是因为位运算快，而是因为缓存命中率高。这里要澄清一个误区：时间和空间是两码事，不存在什么「时空守恒」。省内存不会自动变快，但省内存让数据进入更快的存储层级，这才是变快的原因。

「自动变速箱」构想

盯着各方案的内存对比表，我突然想到一个问题：为什么不能根据数据密度自动选择存储方式？

• 素数密度高的时候（小范围），用位图紧凑存储，访问快；
• 素数密度低的时候（大范围），只记录素数的位置（True的下标），内存省；
• 密度变了就自动「换挡」。

我把这个想法叫做「自动变速箱」：

但有个关键问题：什么时候换挡？如果每次赋值都检查密度并可能触发换挡，那性能就完蛋了——换挡要重建整个内部结构，O(n)的开销。正确答案是：换挡只在两个时机发生——创建数组时，和调用optimize()时。平时insert、pop、赋值都不换挡，待在当前挡位里跑。我当时觉得这个想法太妙了，当晚就开干。

自己造轮子，造了十几天，差点放弃

• 第一天：写了个能跑的原型，位图用bytearray，稀疏用array('I')存下标，开心。
• 第二天：换挡阈值写死50%，结果数据在阈值附近波动时疯狂来回切，性能比不切还差。
• 第三天：加了滞回区间防抖动，但判断逻辑写错了，稀疏区和位图区数据对不上。
• 第四天：稀疏区下标越界不报错，静默写错位置，筛出来的素数里混进了一堆合数。
• 第五天：想支持切片赋值（arr[i*i:n+1:i] = False），结果步长切片和稀疏区的下标表完全对不上。
• 第六天：按位取反写出来了，但取反后count(True)对不上——稀疏区取反后忘了把True和False互换。
• 第七天：in操作符支持了，但每次都全量扫描，比list还慢。
• 第八天：缓存了素数个数，数据一变缓存没失效，数字忽大忽小。
• 第九天：换挡函数写好了，但千万级数据一换挡就卡好几秒。
• 第十天：pickle序列化存进去再读出来，内部结构全乱了。
• 第十一天：写了查找前一个素数的功能（类似rindex），稀疏区返回的是下标表里的位置，不是数组里的真实位置。
• 第十二天：盯着2000行代码，发现边界条件多到数不清，心态崩了。

第十二天晚上，我意识到一个人从零造一个生产级的混合布尔数组，不是十几天能搞定的事。我决定去社区问问。

转机：发帖求助，评论区集体推荐同一个库

我把踩坑经历整理成帖子发了出去，标题是：

「Python筛10亿素数，list爆内存、numpy爆拷贝、bitarray不支持稀疏，我该怎么办？」

评论区画风出奇地一致。第一条高赞评论直接点醒了我：

「你那个『自动变速箱』想法，bool-hybrid-array已经实现了。关键是它换挡只在创建时和optimize()时发生，平时操作不换挡，所以不会抖。你之前写的换挡逻辑之所以崩，是因为你把换挡做成了高频操作——换挡是低频的，别每次赋值都换。」

后面的评论也全是推荐：

• 「直接pip install bool-hybrid-array，你这个素数筛场景它天生适合。」
• 「我筛过100亿以内素数，稀疏场景内存比bitarray还省。」
• 「它有memory_usage(detail=True)，自己看真实内存。」
• 「密集区底层就是numpy，稀疏区用array存下标，两边都是成熟方案。」
• 「月下载过万，不是玩具项目。」
• 「支持np.array(arr)直接转numpy，你的筛法逻辑不用改。」
• 「MIT协议，随便用。」
• 「Python 3.9到3.14全支持，PyPy也行。」
• 「它的find和rindex返回的是数组真实位置，不是下标表位置。」

说实话，评论区全在夸同一个库，看着像水军。但我想：是不是水军跟我没关系，跑一下就知道了。

frombool_hybrid_arrayimportBoolHybridArr# 筛10亿以内素数n=1_000_000_000is_prime=BoolHybridArr([True]*(n+1))is_prime[0]=is_prime[1]=Falseforiinrange(2,int(n**0.5)+1):ifis_prime[i]:is_prime[i*i:n+1:i]=False# 优化一下存储is_prime.optimize()print(is_prime.memory_usage(detail=True))

跑出来的数字让我愣了一下。10亿个布尔值，筛完之后（素数密度约4%，即稀疏场景），内存占用只有几十MB。我用tracemalloc独立验证了一遍，数字对得上。但我必须说清楚：memory_usage(detail=True)是库自己算的，不是第三方审计的。我用tracemalloc测出来跟它对得上，但「对得上」不等于「永远对得上」。别信我，也别信它，信你自己的测量。

同类方案横向对比：素数筛场景谁更强

RoaringBitmap：集合王者，但不是数组

素数筛本质上就是「找出所有素数的下标」，这听起来很像集合操作。RoaringBitmap是整数集合的工业标准：

fromroaringbitmapimportRoaringBitmap primes=RoaringBitmap(range(2,n+1))# 然后逐个剔除非素数...

但问题是：RoaringBitmap存的是集合，不是数组。它没有arr[i]按位置访问的语义，不支持切片赋值arr[i*i:n+1:i] = False，也不保留数组长度。筛素数需要频繁按位置标记和合数，用集合语义写起来非常别扭。

bitarray vs pyarrow vs bool-hybrid-array

中立Benchmark：筛10亿素数

怎么读这张表：

• 初始全True时，bool-hybrid-array用位图模式，内存和numpy一样930MB；
• 筛完后大部分是False（稀疏），调用optimize()后自动切到稀疏模式，内存降到~40MB；
• 速度和numpy接近（因为密集区底层就是numpy），比bitarray快；
• 反向稀疏：如果场景反过来（大部分是True），它会只记False的下标，同样省内存。

注意：均匀分布（50/50）是它和numpy打平的场景，这时候记哪边都省不了。但素数筛是典型的稀疏场景（大范围素数密度低），所以优势明显。

缺点与适用边界：别拿锤子砸所有钉子

第一，optimize()是低频操作，别当高频用。换挡只在创建和optimize()时发生，平时不换挡。如果你在筛法内层循环里反复调optimize()，每次全量重建，性能直接崩。

第二，换挡瞬间是O(n)全量拷贝。从位图切稀疏（或反过来）要遍历整个数组。10亿数据调一次optimize()可能要几秒。但筛素数只需要在筛完后调一次，这个开销可以接受。

第三，非线程安全。多线程并发读写需要自己加锁。

第四，生态年轻。没有numpy那么多文档和社区，遇到冷门问题可能得看源码。

第五，均匀分布打平。50% True / 50% False 的场景，它和numpy内存差不多，没有优势。素数筛在小范围（比如1到1000）素数密度高，这时候它就是位图模式，和numpy一样。

第六，memory_usage(detail=True)是自报数据。我用tracemalloc验证过对得上，但生产环境请自己测。

适用场景：稀疏布尔数组 + 需要数组语义 + 动态操作 + 单线程。素数筛、用户标签、URL去重标记、布隆过滤器的位图层，这些都是它的主场。

不适用场景：纯集合运算（用RoaringBitmap）、均匀分布的定长密集数组（用numpy）、多线程高并发（自己加锁或换方案）。

写在最后

用bool-hybrid-array重写素数筛后，10亿以内素数筛完只要约40MB内存，速度和numpy差不多。我甚至试了100亿，内存也才几百MB，在我的笔记本上就能跑。安装就一行：

pipinstallbool-hybrid-array

项目在Gitee和GitHub上都有（搜bool-hybrid-array），MIT协议。核心类是BoolHybridArr，API和numpy高度兼容，np.array(arr)就能无缝接入现有代码。最后说一句：作者承诺了no removal policy，现有公开接口不会被删除。但接口行为细节可能随版本变化，上生产前务必在你自己的数据和环境里跑一遍。别信我，信你自己的测量。