第一幕崩潰的實(shí)習(xí)生與“不可能完成的任務(wù)”周一早晨陽光透過百葉窗灑在工位上但實(shí)習(xí)生小劉的臉色卻比陰天還難看。他抱著筆記本電腦像抱著炸藥包一樣沖到楊工桌前?！皸罟ぞ让　毙⒌穆曇衾飵е耷弧袄习遄屛野逊?wù)器上的 500G 日志文件按時(shí)間戳排序可我剛跑了幾分鐘程序就崩了報(bào)OutOfMemoryError咱們服務(wù)器內(nèi)存不是有 64G 嗎怎么還是不夠”楊工正端著保溫杯慢悠悠地吹了吹浮沫抬眼看了看小劉屏幕上的報(bào)錯(cuò)信息笑了“500G 的數(shù)據(jù)你指望一次性全塞進(jìn)內(nèi)存里排別說咱們服務(wù)器就是把你賣了換內(nèi)存條也不夠啊。”小劉撓了撓頭一臉委屈“可是Arrays.sort()和Collections.sort()不都是這么用的嗎以前處理幾個(gè) G 的數(shù)據(jù)都沒事啊?！薄耙郧笆且郧艾F(xiàn)在是大數(shù)據(jù)時(shí)代?！睏罟し畔卤永^一把椅子讓小劉坐下“當(dāng)數(shù)據(jù)量大到內(nèi)存裝不下時(shí)我們就不能再用‘內(nèi)部排序’的思維了得請出今天的主角——外部排序。”“外部排序”小劉眼睛一亮“聽起來像是個(gè)高級算法?！薄安凰皇且粋€(gè)單一的算法而是一套策略?！睏罟つ闷鸢装骞P在白板上寫下四個(gè)大字分而治之。第二幕切蛋糕——把大象裝進(jìn)冰箱“來想象一下你面前有一個(gè) 500G 的大蛋糕但你只有一個(gè)能裝 4G 奶油的小盒子內(nèi)存。你怎么把蛋糕整理好”楊工問。小劉想了想“切塊一次切一塊放進(jìn)盒子里弄好再拿出來”“賓果”楊工打了個(gè)響指“這就是外部排序的第一步分塊Chunking?！睏罟ぴ诎装迳袭嬃艘粋€(gè)巨大的長方形代表 500G 文件然后畫了一條虛線把它切成無數(shù)個(gè)小方塊?！拔覀兊膬?nèi)存限制是 4G。為了穩(wěn)妥我們不能把 4G 全占滿得留點(diǎn)空間給操作系統(tǒng)和排序算法的遞歸棧。假設(shè)我們每次只讀3.5G數(shù)據(jù)進(jìn)內(nèi)存?！庇?jì)算時(shí)間500÷3.5≈143500÷3.5≈143 。結(jié)論我們需要把這 500G 數(shù)據(jù)切成大約143 個(gè)小文件?！暗谝徊讲僮骱芎唵巍睏罟み厡戇呎f“寫一個(gè)循環(huán)每次從原文件讀取 3.5G 數(shù)據(jù)到內(nèi)存緩沖區(qū)。這就好比把大蛋糕切成了 143 塊小蛋糕?！钡谌桓鱾€(gè)擊破——內(nèi)存里的極速排序“切好之后呢”小劉問?！扒泻弥筮@ 3.5G 數(shù)據(jù)就在內(nèi)存里了這時(shí)候它就是個(gè)普通的小數(shù)組?！睏罟ぴ诎装宓拿總€(gè)小方塊上寫了個(gè)“Sort”?！斑@時(shí)候你就可以盡情使用你熟悉的快速排序或者歸并排序了。甚至直接調(diào)用語言自帶的排序庫比如 Java 的Arrays.sort()或 C 的std::sort。這些算法在內(nèi)存里的速度是非常快的?！睏罟?qiáng)調(diào)道“排好序后立刻把這個(gè)有序的 3.5G 數(shù)據(jù)寫回磁盤命名為temp_001.dattemp_002.dat……以此類推。注意這時(shí)候每個(gè)小文件內(nèi)部都是有序的了”小劉恍然大悟“哦所以我先產(chǎn)生了 143 個(gè)‘局部有序’的小文件”“對這就是第二步內(nèi)部排序?！睏罟c(diǎn)頭“現(xiàn)在難題從‘如何排序 500G 數(shù)據(jù)’變成了‘如何合并 143 個(gè)有序小文件’?！钡谒哪粵Q戰(zhàn)時(shí)刻——多路歸并與最小堆小劉看著白板上的 143 個(gè)小方塊又犯了難“楊工合并我會(huì)啊。我把temp_001和temp_002合并成一個(gè)新的再和temp_003合并……就像歸并排序那樣兩兩合并行不行”楊工搖搖頭“理論上可行但效率太低。你要知道磁盤 I/O 是最慢的。如果你兩兩合并這 143 個(gè)文件要反反復(fù)復(fù)讀寫磁盤好多輪硬盤會(huì)冒煙的?！薄澳窃趺崔k143 個(gè)文件一起讀那內(nèi)存又爆了”“這就是最精彩的部分——多路歸并K-way Merge?！睏罟ぴ诎装迳袭嬃艘粋€(gè)漏斗形狀的結(jié)構(gòu)上面是 143 根管子下面匯聚成一根管子?！拔覀儾恍枰?143 個(gè)文件的內(nèi)容全讀進(jìn)內(nèi)存我們只需要維護(hù)一個(gè)最小堆Min-Heap?！睏罟ら_始畫圖講解核心邏輯建立緩沖區(qū)我們在內(nèi)存里為這 143 個(gè)文件每個(gè)開辟一個(gè)小窗口比如每個(gè)文件只讀 1MB 到內(nèi)存緩沖區(qū)。這樣 143MB 的內(nèi)存占用微乎其微。初始化堆從每個(gè)文件的緩沖區(qū)里取出第一個(gè)元素也就是該文件當(dāng)前的最小值扔進(jìn)一個(gè)大小為 143 的最小堆里。取最小值堆頂?shù)脑匾欢ㄊ撬形募锶肿钚〉哪莻€(gè)把它拿出來寫入最終的result.dat文件。補(bǔ)充元素堆頂元素被拿走了空了一個(gè)位置。那就從剛才那個(gè)元素所屬的文件里再讀一個(gè)下一個(gè)元素補(bǔ)進(jìn)去調(diào)整堆結(jié)構(gòu)。循環(huán)重復(fù)步驟 3 和 4直到所有文件都讀完。小劉盯著圖看了半天突然拍大腿“我懂了這就好比 143 個(gè)賽跑選手每個(gè)人手里拿著一張寫著時(shí)間的卡片。裁判堆每次只看誰手里的卡片數(shù)字最小就把誰的成績記錄到總榜上然后讓那個(gè)人再掏出一張新卡片。裁判不需要知道所有人所有的成績只需要盯著眼前的 143 張卡片就行”“比喻非常精準(zhǔn)”楊工豎起大拇指“這就是用極小的內(nèi)存代價(jià)完成了海量數(shù)據(jù)的有序合并?！钡谖迥桓呤值倪M(jìn)階——置換選擇排序小劉興奮地收拾東西準(zhǔn)備去寫代碼楊工叫住了他“等等還有個(gè)進(jìn)階技巧如果你想讓老板對你刮目相看可以用上這個(gè)?！薄斑€有更厲害的”“剛才我們說每個(gè)小塊只能排 3.5G對吧”楊工神秘一笑“其實(shí)利用堆的特性我們可以生成平均長度為 2 倍內(nèi)存大小的有序塊。這叫置換選擇排序?！薄霸趺醋龅降摹薄霸跉w并或者生成初始塊的時(shí)候如果新讀進(jìn)來的元素比當(dāng)前輸出的元素小它肯定不能排在后面。普通做法是把它留到下一輪。但在置換選擇里我們可以把它暫時(shí)‘凍結(jié)’在堆的葉子節(jié)點(diǎn)不參與當(dāng)前輪的比較等這一輪結(jié)束了再解凍。這樣原本只能裝 3.5G 的內(nèi)存平均能產(chǎn)出 7G 的有序塊”楊工總結(jié)道“這意味著你的臨時(shí)文件數(shù)量直接從 143 個(gè)減少到 70 多個(gè)歸并時(shí)的 I/O 壓力直接減半”尾聲代碼跑通的那一刻兩個(gè)小時(shí)后服務(wù)器機(jī)房傳來風(fēng)扇的轟鳴聲。小劉盯著終端屏幕上跳動(dòng)的進(jìn)度條最終顯示Sort Completed. Time: 45m 20s?！俺闪恕毙g呼道“500G 數(shù)據(jù)4G 內(nèi)存限制完美排序”楊工走過來看了一眼日志“不錯(cuò)。記住今天的教訓(xùn)在大數(shù)據(jù)面前內(nèi)存是昂貴的奢侈品磁盤才是我們堅(jiān)實(shí)的依靠。學(xué)會(huì)尊重 I/O學(xué)會(huì)分而治之這才是工程師的思維?！毙⒂昧c(diǎn)點(diǎn)頭在筆記本上重重地寫下了一行字外部排序 分塊內(nèi)排 多路歸并最小堆。