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