「部分情節為虛構演繹僅供參考」事情是這樣的。那天我在刷算法題遇到一道經典題篩出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現有公開接口不會被刪除。但接口行為細節可能隨版本變化上生產前務必在你自己的數據和環境里跑一遍。別信我信你自己的測量。