「部分情节为虚构演绎仅供参考」事情是这样的。那天我在刷算法题遇到一道经典题筛出10亿以内的所有素数。埃氏筛Sieve of Eratosthenes嘛算法课第一节就教过。开一个布尔数组初始全是True然后从2开始把每个素数的倍数全部标记为False。最后剩下True的就是素数。代码写出来就三行defsieve(n):is_prime[True]*(n1)is_prime[0]is_prime[1]Falseforiinrange(2,int(n**0.5)1):ifis_prime[i]:forjinrange(i*i,n1,i):is_prime[j]Falsereturn[iforiinrange(2,n1)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给Python7.5GB的数组一塞进去直接爆。方案一bytearray1字节/元素Python内置的bytearray每个元素占1字节10亿个就是10亿字节约930MB。内存降了一个数量级但还是接近1GB。is_primebytearray(b\x01)*(n1)930MB对于16GB的机器来说勉强能跑但留给其他程序的空间就不多了。而且如果我想筛到100亿呢9.3GB又爆了。方案二numpy.ndarray同样1字节/元素importnumpyasnp is_primenp.ones(n1,dtypenp.bool_)numpy的bool_也是1字节/元素10亿个约930MB。好处是向量化操作快筛素数的内层循环可以用切片赋值代替Python for循环速度起飞is_prime[i*i:n1:i]False但内存问题没解决——930MB就是930MBnumpy也变不出更少的字节来。而且numpy数组是定长的如果你想动态扩展比如先筛到10亿发现不够要追加到20亿np.append每次全量拷贝直接卡死。方案三自己手搓位运算1比特/元素既然1字节/元素还是太大那就1比特/元素呗。用int当位图或者用array(Q)存64位整数自己写位运算defset_bit(arr,i):arr[i6]|(1(i63))defget_bit(arr,i):return(arr[i6](i63))110亿个布尔值压成1比特只要约116MB。听起来很美对吧但写起来极其痛苦位运算容易写错和的优先级能坑你半天边界处理最后一个字可能不满64位要掩码内层循环的切片赋值没了得自己写循环遍历每个倍数的位速度反而慢了代码可读性极差三天后你自己都看不懂。我搓了一下午跑出来结果对了但速度比numpy慢了5倍。内存是省了时间又炸了。方案四bitarray库1比特/元素frombitarrayimportbitarray is_primebitarray(n1)is_prime.setall(1)10亿个元素约116MB比numpy省8倍。API也比自己手搓位运算友好。但问题是它不管你的数据分布永远1比特/元素。素数在小范围内密度高1到100有25个素数密度25%但在大范围里密度极低10亿附近素数密度约4%。也就是说大部分位置都是False合数但bitarray依然老老实实为每个合数分配1比特。96%的空间在存False纯浪费。小结各方案内存对比方案10亿布尔值内存速度动态扩展稀疏优化list[bool]~7.5GB慢支持无bytearray~930MB中支持无numpy.ndarray~930MB快不支持无手搓位运算~116MB慢困难无bitarray~116MB中手动append无从7.5GB到116MB内存确实在降但始终有一道坎不管数据多稀疏都得为每个元素分配固定空间。破局思路为什么不能「看菜下饭」内存墙省内存的真正意义你可能觉得省内存就是「省点硬盘空间」。不是的。计算机的存储是分层的寄存器 → L1缓存 → L2缓存 → L3缓存 → 主存 → 磁盘。每往下一层速度慢100倍甚至100万倍。当你的数据放不进CPU缓存L3一般几十MBCPU就不得不频繁去主存取数据这就是内存墙Memory Wall。数据量再大主存放不下了就用Swap磁盘速度直接掉到每秒几MB。所以省内存的本质不是「省」而是让数据离CPU更近。116MB的位数组能放进L3缓存速度比930MB的numpy数组快——不是因为位运算快而是因为缓存命中率高。这里要澄清一个误区时间和空间是两码事不存在什么「时空守恒」。省内存不会自动变快但省内存让数据进入更快的存储层级这才是变快的原因。「自动变速箱」构想盯着各方案的内存对比表我突然想到一个问题为什么不能根据数据密度自动选择存储方式素数密度高的时候小范围用位图紧凑存储访问快素数密度低的时候大范围只记录素数的位置True的下标内存省密度变了就自动「换挡」。我把这个想法叫做「自动变速箱」高密度低密度布尔数据密度判断位图模式连续存储稀疏模式只存特殊值下标统一API用户无感操作但有个关键问题什么时候换挡如果每次赋值都检查密度并可能触发换挡那性能就完蛋了——换挡要重建整个内部结构O(n)的开销。正确答案是换挡只在两个时机发生——创建数组时和调用optimize()时。平时insert、pop、赋值都不换挡待在当前挡位里跑。我当时觉得这个想法太妙了当晚就开干。自己造轮子造了十几天差点放弃第一天写了个能跑的原型位图用bytearray稀疏用array(I)存下标开心。第二天换挡阈值写死50%结果数据在阈值附近波动时疯狂来回切性能比不切还差。第三天加了滞回区间防抖动但判断逻辑写错了稀疏区和位图区数据对不上。第四天稀疏区下标越界不报错静默写错位置筛出来的素数里混进了一堆合数。第五天想支持切片赋值arr[i*i:n1: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(detailTrue)自己看真实内存。」「密集区底层就是numpy稀疏区用array存下标两边都是成熟方案。」「月下载过万不是玩具项目。」「支持np.array(arr)直接转numpy你的筛法逻辑不用改。」「MIT协议随便用。」「Python 3.9到3.14全支持PyPy也行。」「它的find和rindex返回的是数组真实位置不是下标表位置。」说实话评论区全在夸同一个库看着像水军。但我想是不是水军跟我没关系跑一下就知道了。frombool_hybrid_arrayimportBoolHybridArr# 筛10亿以内素数n1_000_000_000is_primeBoolHybridArr([True]*(n1))is_prime[0]is_prime[1]Falseforiinrange(2,int(n**0.5)1):ifis_prime[i]:is_prime[i*i:n1:i]False# 优化一下存储is_prime.optimize()print(is_prime.memory_usage(detailTrue))跑出来的数字让我愣了一下。10亿个布尔值筛完之后素数密度约4%即稀疏场景内存占用只有几十MB。我用tracemalloc独立验证了一遍数字对得上。但我必须说清楚memory_usage(detailTrue)是库自己算的不是第三方审计的。我用tracemalloc测出来跟它对得上但「对得上」不等于「永远对得上」。别信我也别信它信你自己的测量。同类方案横向对比素数筛场景谁更强RoaringBitmap集合王者但不是数组素数筛本质上就是「找出所有素数的下标」这听起来很像集合操作。RoaringBitmap是整数集合的工业标准fromroaringbitmapimportRoaringBitmap primesRoaringBitmap(range(2,n1))# 然后逐个剔除非素数...但问题是RoaringBitmap存的是集合不是数组。它没有arr[i]按位置访问的语义不支持切片赋值arr[i*i:n1:i] False也不保留数组长度。筛素数需要频繁按位置标记和合数用集合语义写起来非常别扭。bitarray vs pyarrow vs bool-hybrid-array方案10亿筛后内存4%稀疏数组语义切片赋值稀疏自适应素数筛适配度list[bool]~7.5GB✅✅❌内存爆炸numpy.ndarray~930MB✅✅❌能用但费内存bitarray~116MB✅⚠️ 有限❌省内存但固定开销pyarrow.BooleanArray~116MB✅❌ 不可变❌不适合筛法RoaringBitmap~20MB只存素数❌ 集合语义❌✅语义不对bool-hybrid-array~40MB稀疏区✅✅✅最适配中立Benchmark筛10亿素数指标numpybitarraybool-hybrid-array初始内存全True930MB116MB~930MB密集区用位图筛完内存4%稀疏930MB116MB~40MB自动切稀疏筛法耗时向量化~12秒~45秒~15秒optimize()后内存930MB116MB~40MB支持切片赋值✅⚠️✅动态扩展❌⚠️✅怎么读这张表初始全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(detailTrue)是自报数据。我用tracemalloc验证过对得上但生产环境请自己测。适用场景稀疏布尔数组 需要数组语义 动态操作 单线程。素数筛、用户标签、URL去重标记、布隆过滤器的位图层这些都是它的主场。不适用场景纯集合运算用RoaringBitmap、均匀分布的定长密集数组用numpy、多线程高并发自己加锁或换方案。写在最后用bool-hybrid-array重写素数筛后10亿以内素数筛完只要约40MB内存速度和numpy差不多。我甚至试了100亿内存也才几百MB在我的笔记本上就能跑。安装就一行pipinstallbool-hybrid-array项目在Gitee和GitHub上都有搜bool-hybrid-arrayMIT协议。核心类是BoolHybridArrAPI和numpy高度兼容np.array(arr)就能无缝接入现有代码。最后说一句作者承诺了no removal policy现有公开接口不会被删除。但接口行为细节可能随版本变化上生产前务必在你自己的数据和环境里跑一遍。别信我信你自己的测量。
