架構(gòu)師的邏輯技術(shù)思維分析(編輯修改稿)
2025-07-24 04:53 本頁面
【文章內(nèi)容簡介】 切分成若干小問題來解決。那么8G內(nèi)存的計算機(jī)一次大概能排多大的數(shù)據(jù)量，可以在有限的時間內(nèi)排完呢？也就是100G的大文件要怎么切法，切成多少份比較合適？這個是考察候選人的時間空間復(fù)雜度估算能力，需要一定的計算機(jī)組織和算法功底，也需要一定實戰(zhàn)經(jīng)驗和sense。實際上8G內(nèi)存的話，操作系統(tǒng)要用掉一部分，如果用Java開發(fā)排序程序，大致JVM可用2~4G內(nèi)存，基于一般的經(jīng)驗值，一次排1G左右的數(shù)據(jù)應(yīng)該沒有問題（我實際在計算機(jī)上干過1G數(shù)據(jù)的排序，是OK的）。所以100G的文件需要先切分成100份，每份1G，這樣每個子文件可以直接加載到內(nèi)存進(jìn)行排序。對于1G數(shù)據(jù)量的字符串排序，采用Java里頭提供的快速排序算法是比較合適的。好，經(jīng)過有限時間的排序（取決于計算機(jī)性能，快的一天內(nèi)能排完），假定100個1G的文件都已經(jīng)排好了，相當(dāng)于現(xiàn)在硬盤上有100個已經(jīng)排好序的文件，但是我們最終需要的是一個排好序的文件，下面該怎么做？這個時候我們需要把已經(jīng)解決的子問題組合起來，合并成我們需要的最終結(jié)果文件。這個時候該采用什么算法呢？這里考察候選人對外排序和歸并排序算法的掌握程度，我們可以將100個排好序的文件進(jìn)行兩兩歸并排序，這樣不斷重復(fù)，我們就會得到50個排好序的文件，每個大小是2G。然后再兩兩歸并，不斷重復(fù)，直到最后兩個文件歸并成目標(biāo)文件，這個文件就是100G并且是排好序的。因為是外排序+歸并排序，每次只需要讀取當(dāng)前索引指向的文件記錄到內(nèi)存，進(jìn)行比較，小的那個輸出到目標(biāo)文件，內(nèi)存占用極少。另外，上面的算法是兩路歸并，也可以采用多路歸并，甚至是采用堆排序進(jìn)行優(yōu)化，但是總體分治思路沒有變化?？傮w上這是一個非常好的面試題，除了考察候選人的分治思維之外，還考察對各種排序算法（快排，外排序，歸并排序，堆排序）的理解，計算的時間空間復(fù)雜度估算，計算機(jī)的內(nèi)外存特性和組織，文件操作等等。實際上能完全回答清楚這個問題的候選人極少，如果有幸被我面到一個，我會如獲至寶，因為這個人有成長為優(yōu)秀架構(gòu)師的潛質(zhì)。另外，遞歸也是一種特殊的分治技術(shù)，掌握遞歸技術(shù)的開發(fā)人員，相當(dāng)于掌握了一種強(qiáng)大的編程武器，可以解決一些一般開發(fā)人員無法解決的問題。比方說最近我的團(tuán)隊在研發(fā)一款新的服務(wù)框架，其中包括契約解析器(parser)，代碼生產(chǎn)器(code generator)，序列化器(serializer)等組件，里頭大量需要用到遞歸的思維和技術(shù)，沒有這個思維的開發(fā)人員就干不了這個事情。所以我在面試候選人的時候，一般都會出遞歸相關(guān)的編程題，考察候選人的遞歸思維。大自然中遞歸結(jié)
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1