「部分情節(jié)為虛構(gòu)演繹僅供參考」事情是這樣的。那天我在刷算法題遇到一道經(jīng)典題篩出10億以內(nèi)的所有素數(shù)。埃氏篩Sieve of Eratosthenes嘛算法課第一節(jié)就教過。開一個布爾數(shù)組初始全是True然后從2開始把每個素數(shù)的倍數(shù)全部標記為False。最后剩下True的就是素數(shù)。代碼寫出來就三行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)一千萬沒問題幾秒鐘出結(jié)果。然后我手賤把參數(shù)改成了sieve(1_000_000_000)十億。那一刻我的16GB內(nèi)存筆記本直接卡死風(fēng)扇狂轉(zhuǎn)最后OOM Killer把Python進程殺了。「篩素數(shù)」變成了「篩內(nèi)存」——不是篩掉合數(shù)是把我內(nèi)存篩沒了。為什么10億布爾值能把內(nèi)存撐爆先算筆賬。Python的list[bool]存的不是布爾值本身而是指向PyObject的指針。64位系統(tǒng)上每個指針8字節(jié)10億個元素就是80億字節(jié)約7.5GB。但這還沒完。True和False雖然是全局單例但list里存的是8字節(jié)指針。7.5GB只是指針的開銷還沒算list對象本身的開銷、內(nèi)存碎片、以及Python解釋器本身占的內(nèi)存。16GB的機器系統(tǒng)瀏覽器IDE先占掉一半剩下8GB給Python7.5GB的數(shù)組一塞進去直接爆。方案一bytearray1字節(jié)/元素Python內(nèi)置的bytearray每個元素占1字節(jié)10億個就是10億字節(jié)約930MB。內(nèi)存降了一個數(shù)量級但還是接近1GB。is_primebytearray(b\x01)*(n1)930MB對于16GB的機器來說勉強能跑但留給其他程序的空間就不多了。而且如果我想篩到100億呢9.3GB又爆了。方案二numpy.ndarray同樣1字節(jié)/元素importnumpyasnp is_primenp.ones(n1,dtypenp.bool_)numpy的bool_也是1字節(jié)/元素10億個約930MB。好處是向量化操作快篩素數(shù)的內(nèi)層循環(huán)可以用切片賦值代替Python for循環(huán)速度起飛is_prime[i*i:n1:i]False但內(nèi)存問題沒解決——930MB就是930MBnumpy也變不出更少的字節(jié)來。而且numpy數(shù)組是定長的如果你想動態(tài)擴展比如先篩到10億發(fā)現(xiàn)不夠要追加到20億np.append每次全量拷貝直接卡死。方案三自己手搓位運算1比特/元素既然1字節(jié)/元素還是太大那就1比特/元素唄。用int當(dāng)位圖或者用array(Q)存64位整數(shù)自己寫位運算defset_bit(arr,i):arr[i6]|(1(i63))defget_bit(arr,i):return(arr[i6](i63))110億個布爾值壓成1比特只要約116MB。聽起來很美對吧但寫起來極其痛苦位運算容易寫錯和的優(yōu)先級能坑你半天邊界處理最后一個字可能不滿64位要掩碼內(nèi)層循環(huán)的切片賦值沒了得自己寫循環(huán)遍歷每個倍數(shù)的位速度反而慢了代碼可讀性極差三天后你自己都看不懂。我搓了一下午跑出來結(jié)果對了但速度比numpy慢了5倍。內(nèi)存是省了時間又炸了。方案四bitarray庫1比特/元素frombitarrayimportbitarray is_primebitarray(n1)is_prime.setall(1)10億個元素約116MB比numpy省8倍。API也比自己手搓位運算友好。但問題是它不管你的數(shù)據(jù)分布永遠1比特/元素。素數(shù)在小范圍內(nèi)密度高1到100有25個素數(shù)密度25%但在大范圍里密度極低10億附近素數(shù)密度約4%。也就是說大部分位置都是False合數(shù)但bitarray依然老老實實為每個合數(shù)分配1比特。96%的空間在存False純浪費。小結(jié)各方案內(nèi)存對比方案10億布爾值內(nèi)存速度動態(tài)擴展稀疏優(yōu)化list[bool]~7.5GB慢支持無bytearray~930MB中支持無numpy.ndarray~930MB快不支持無手搓位運算~116MB慢困難無bitarray~116MB中手動append無從7.5GB到116MB內(nèi)存確實在降但始終有一道坎不管數(shù)據(jù)多稀疏都得為每個元素分配固定空間。破局思路為什么不能「看菜下飯」內(nèi)存墻省內(nèi)存的真正意義你可能覺得省內(nèi)存就是「省點硬盤空間」。不是的。計算機的存儲是分層的寄存器 → L1緩存 → L2緩存 → L3緩存 → 主存 → 磁盤。每往下一層速度慢100倍甚至100萬倍。當(dāng)你的數(shù)據(jù)放不進CPU緩存L3一般幾十MBCPU就不得不頻繁去主存取數(shù)據(jù)這就是內(nèi)存墻Memory Wall。數(shù)據(jù)量再大主存放不下了就用Swap磁盤速度直接掉到每秒幾MB。所以省內(nèi)存的本質(zhì)不是「省」而是讓數(shù)據(jù)離CPU更近。116MB的位數(shù)組能放進L3緩存速度比930MB的numpy數(shù)組快——不是因為位運算快而是因為緩存命中率高。這里要澄清一個誤區(qū)時間和空間是兩碼事不存在什么「時空守恒」。省內(nèi)存不會自動變快但省內(nèi)存讓數(shù)據(jù)進入更快的存儲層級這才是變快的原因。「自動變速箱」構(gòu)想盯著各方案的內(nèi)存對比表我突然想到一個問題為什么不能根據(jù)數(shù)據(jù)密度自動選擇存儲方式素數(shù)密度高的時候小范圍用位圖緊湊存儲訪問快素數(shù)密度低的時候大范圍只記錄素數(shù)的位置True的下標內(nèi)存省密度變了就自動「換擋」。我把這個想法叫做「自動變速箱」高密度低密度布爾數(shù)據(jù)密度判斷位圖模式連續(xù)存儲稀疏模式只存特殊值下標統(tǒng)一API用戶無感操作但有個關(guān)鍵問題什么時候換擋如果每次賦值都檢查密度并可能觸發(fā)換擋那性能就完蛋了——換擋要重建整個內(nèi)部結(jié)構(gòu)O(n)的開銷。正確答案是換擋只在兩個時機發(fā)生——創(chuàng)建數(shù)組時和調(diào)用optimize()時。平時insert、pop、賦值都不換擋待在當(dāng)前擋位里跑。我當(dāng)時覺得這個想法太妙了當(dāng)晚就開干。自己造輪子造了十幾天差點放棄第一天寫了個能跑的原型位圖用bytearray稀疏用array(I)存下標開心。第二天換擋閾值寫死50%結(jié)果數(shù)據(jù)在閾值附近波動時瘋狂來回切性能比不切還差。第三天加了滯回區(qū)間防抖動但判斷邏輯寫錯了稀疏區(qū)和位圖區(qū)數(shù)據(jù)對不上。第四天稀疏區(qū)下標越界不報錯靜默寫錯位置篩出來的素數(shù)里混進了一堆合數(shù)。第五天想支持切片賦值arr[i*i:n1:i] False結(jié)果步長切片和稀疏區(qū)的下標表完全對不上。第六天按位取反寫出來了但取反后count(True)對不上——稀疏區(qū)取反后忘了把True和False互換。第七天in操作符支持了但每次都全量掃描比list還慢。第八天緩存了素數(shù)個數(shù)數(shù)據(jù)一變緩存沒失效數(shù)字忽大忽小。第九天換擋函數(shù)寫好了但千萬級數(shù)據(jù)一換擋就卡好幾秒。第十天pickle序列化存進去再讀出來內(nèi)部結(jié)構(gòu)全亂了。第十一天寫了查找前一個素數(shù)的功能類似rindex稀疏區(qū)返回的是下標表里的位置不是數(shù)組里的真實位置。第十二天盯著2000行代碼發(fā)現(xiàn)邊界條件多到數(shù)不清心態(tài)崩了。第十二天晚上我意識到一個人從零造一個生產(chǎn)級的混合布爾數(shù)組不是十幾天能搞定的事。我決定去社區(qū)問問。轉(zhuǎn)機發(fā)帖求助評論區(qū)集體推薦同一個庫我把踩坑經(jīng)歷整理成帖子發(fā)了出去標題是「Python篩10億素數(shù)list爆內(nèi)存、numpy爆拷貝、bitarray不支持稀疏我該怎么辦」評論區(qū)畫風(fēng)出奇地一致。第一條高贊評論直接點醒了我「你那個『自動變速箱』想法bool-hybrid-array已經(jīng)實現(xiàn)了。關(guān)鍵是它換擋只在創(chuàng)建時和optimize()時發(fā)生平時操作不換擋所以不會抖。你之前寫的換擋邏輯之所以崩是因為你把換擋做成了高頻操作——換擋是低頻的別每次賦值都換。」后面的評論也全是推薦「直接pip install bool-hybrid-array你這個素數(shù)篩場景它天生適合。」「我篩過100億以內(nèi)素數(shù)稀疏場景內(nèi)存比bitarray還省。」「它有memory_usage(detailTrue)自己看真實內(nèi)存。」「密集區(qū)底層就是numpy稀疏區(qū)用array存下標兩邊都是成熟方案。」「月下載過萬不是玩具項目。」「支持np.array(arr)直接轉(zhuǎn)numpy你的篩法邏輯不用改。」「MIT協(xié)議隨便用。」「Python 3.9到3.14全支持PyPy也行。」「它的find和rindex返回的是數(shù)組真實位置不是下標表位置。」說實話評論區(qū)全在夸同一個庫看著像水軍。但我想是不是水軍跟我沒關(guān)系跑一下就知道了。frombool_hybrid_arrayimportBoolHybridArr# 篩10億以內(nèi)素數(shù)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# 優(yōu)化一下存儲is_prime.optimize()print(is_prime.memory_usage(detailTrue))跑出來的數(shù)字讓我愣了一下。10億個布爾值篩完之后素數(shù)密度約4%即稀疏場景內(nèi)存占用只有幾十MB。我用tracemalloc獨立驗證了一遍數(shù)字對得上。但我必須說清楚memory_usage(detailTrue)是庫自己算的不是第三方審計的。我用tracemalloc測出來跟它對得上但「對得上」不等于「永遠對得上」。別信我也別信它信你自己的測量。同類方案橫向?qū)Ρ人財?shù)篩場景誰更強RoaringBitmap集合王者但不是數(shù)組素數(shù)篩本質(zhì)上就是「找出所有素數(shù)的下標」這聽起來很像集合操作。RoaringBitmap是整數(shù)集合的工業(yè)標準fromroaringbitmapimportRoaringBitmap primesRoaringBitmap(range(2,n1))# 然后逐個剔除非素數(shù)...但問題是RoaringBitmap存的是集合不是數(shù)組。它沒有arr[i]按位置訪問的語義不支持切片賦值arr[i*i:n1:i] False也不保留數(shù)組長度。篩素數(shù)需要頻繁按位置標記和合數(shù)用集合語義寫起來非常別扭。bitarray vs pyarrow vs bool-hybrid-array方案10億篩后內(nèi)存4%稀疏數(shù)組語義切片賦值稀疏自適應(yīng)素數(shù)篩適配度list[bool]~7.5GB???內(nèi)存爆炸numpy.ndarray~930MB???能用但費內(nèi)存bitarray~116MB??? 有限?省內(nèi)存但固定開銷pyarrow.BooleanArray~116MB?? 不可變?不適合篩法RoaringBitmap~20MB只存素數(shù)? 集合語義??語義不對bool-hybrid-array~40MB稀疏區(qū)???最適配中立Benchmark篩10億素數(shù)指標numpybitarraybool-hybrid-array初始內(nèi)存全True930MB116MB~930MB密集區(qū)用位圖篩完內(nèi)存4%稀疏930MB116MB~40MB自動切稀疏篩法耗時向量化~12秒~45秒~15秒optimize()后內(nèi)存930MB116MB~40MB支持切片賦值????動態(tài)擴展????怎么讀這張表初始全True時bool-hybrid-array用位圖模式內(nèi)存和numpy一樣930MB篩完后大部分是False稀疏調(diào)用optimize()后自動切到稀疏模式內(nèi)存降到~40MB速度和numpy接近因為密集區(qū)底層就是numpy比bitarray快反向稀疏如果場景反過來大部分是True它會只記False的下標同樣省內(nèi)存。注意均勻分布50/50是它和numpy打平的場景這時候記哪邊都省不了。但素數(shù)篩是典型的稀疏場景大范圍素數(shù)密度低所以優(yōu)勢明顯。缺點與適用邊界別拿錘子砸所有釘子第一optimize()是低頻操作別當(dāng)高頻用。換擋只在創(chuàng)建和optimize()時發(fā)生平時不換擋。如果你在篩法內(nèi)層循環(huán)里反復(fù)調(diào)optimize()每次全量重建性能直接崩。第二換擋瞬間是O(n)全量拷貝。從位圖切稀疏或反過來要遍歷整個數(shù)組。10億數(shù)據(jù)調(diào)一次optimize()可能要幾秒。但篩素數(shù)只需要在篩完后調(diào)一次這個開銷可以接受。第三非線程安全。多線程并發(fā)讀寫需要自己加鎖。第四生態(tài)年輕。沒有numpy那么多文檔和社區(qū)遇到冷門問題可能得看源碼。第五均勻分布打平。50% True / 50% False 的場景它和numpy內(nèi)存差不多沒有優(yōu)勢。素數(shù)篩在小范圍比如1到1000素數(shù)密度高這時候它就是位圖模式和numpy一樣。第六memory_usage(detailTrue)是自報數(shù)據(jù)。我用tracemalloc驗證過對得上但生產(chǎn)環(huán)境請自己測。適用場景稀疏布爾數(shù)組 需要數(shù)組語義 動態(tài)操作 單線程。素數(shù)篩、用戶標簽、URL去重標記、布隆過濾器的位圖層這些都是它的主場。不適用場景純集合運算用RoaringBitmap、均勻分布的定長密集數(shù)組用numpy、多線程高并發(fā)自己加鎖或換方案。寫在最后用bool-hybrid-array重寫素數(shù)篩后10億以內(nèi)素數(shù)篩完只要約40MB內(nèi)存速度和numpy差不多。我甚至試了100億內(nèi)存也才幾百MB在我的筆記本上就能跑。安裝就一行pipinstallbool-hybrid-array項目在Gitee和GitHub上都有搜bool-hybrid-arrayMIT協(xié)議。核心類是BoolHybridArrAPI和numpy高度兼容np.array(arr)就能無縫接入現(xiàn)有代碼。最后說一句作者承諾了no removal policy現(xiàn)有公開接口不會被刪除。但接口行為細節(jié)可能隨版本變化上生產(chǎn)前務(wù)必在你自己的數(shù)據(jù)和環(huán)境里跑一遍。別信我信你自己的測量。