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