丨分治算法談一談大規(guī)模計(jì)算框架mapreduce中思想

這個(gè)定義看起來有點(diǎn)類似遞歸的定義。關(guān)于分治和遞歸的區(qū)別，我們?cè)谂判颍ㄏ拢┑臅r(shí)候講過，分治算法是一種處理問題的思想，遞歸是一種編程技巧。實(shí)際上，分治算法一般都比較假設(shè)我們有n個(gè)數(shù)據(jù)，我們期望數(shù)據(jù)從小到大排列，那完全有序的數(shù)據(jù)的有序度就是n(n-1)/2，逆序度等于0；相反，倒序排列的數(shù)據(jù)的有序度就是0，逆序度是n(n-1)/2。除了這最笨的方法是，拿每個(gè)數(shù)字跟它后面的數(shù)字比較，看有幾個(gè)比它小的。我們把比它小的數(shù)字個(gè)數(shù)記作k，通過這樣的方式，把每個(gè)數(shù)字都一遍之后，然后對(duì)每個(gè)數(shù)字對(duì)應(yīng)的k值求和，最后得到的總和就是逆序?qū)€(gè)數(shù)。不過，這樣操作的時(shí)間復(fù)雜度是O(n^2)。那有沒有更加高效的處理方法呢？我們用分治算法來試試。我們套用分治的思想來求數(shù)組A的逆序?qū)€(gè)數(shù)。我們可以將數(shù)組分成前后兩半A1和A2分別計(jì)算A1和A2的逆序?qū)€(gè)數(shù)K1和K2，然后再計(jì)算A1與A2之間的逆序?qū)€(gè)數(shù)K3那數(shù)組A的逆序?qū)€(gè)數(shù)就等于K1+K2+K3。我們前面講過，使用分治算法其中一個(gè)要求是，子問題合并的代價(jià)不能太大，否則就起不了降低時(shí)間復(fù)雜度的效果了。那回到這個(gè)問題，如何快速計(jì)算出兩個(gè)子問題A1與A2之間的逆序?qū)€(gè)數(shù)呢？歸并排序中有一個(gè)非常關(guān)鍵的操作，就是將兩個(gè)有序的小數(shù)組，合并成一個(gè)有序的數(shù)組。實(shí)際上，在這個(gè)合并的過程中，我們就可以計(jì)算這兩個(gè)小數(shù)組的逆序?qū)€(gè)數(shù)了。每次合并操作，我們都計(jì)算逆序?qū)€(gè)數(shù)，把這些計(jì)算出來的逆序?qū)€(gè)數(shù)求和，就是這個(gè)數(shù)組的逆序?qū)€(gè)數(shù)了。1privateintnum=0;//2publicintcount(int[]a,intn)num=mergeSortCounting(a,0,n-return78privatevoidmergeSortCounting(int[]a,intp,intr)if(p>=r)intq=mergeSortCounting(a,p,mergeSortCounting(a,q+1,merge(a,p,q,1517privatevoidmerge(int[]a,intp,intq,intr) inti=p,j=q+1,k=int[]tmp=newint[r-while(i<=q&&j<=r)if(a[i]<=a[j])tmp[k++]=}elsenum+=(q-i+1);//統(tǒng)計(jì)p-q之間，比a[j]tmp[k++]=}}while(i<=q){//tmp[k++]=}while(j<=r){//tmp[k++]=}for(i0;ir-p;++i)tmp拷貝回a[p+i]=}}有很多同學(xué)經(jīng)常說，某某算法思想如此巧妙，我是怎么也想不到的。實(shí)際上，確實(shí)是的。有些算法確實(shí)非常巧妙，并不是每個(gè)人短時(shí)間都能想到的。比如這個(gè)問題，并不是每個(gè)人都能想到可以借助歸并排序算法來解決，不夸張地說，如果之前沒接觸過，絕大部分人都想不到。但是，如果我告訴你可以借助歸并排序算法來解決，那你就應(yīng)該要想到如何改造歸并排序，來求解這個(gè)問題了，只要你能做到這一點(diǎn)，我覺得就很棒了。二維平面上有n個(gè)點(diǎn)，如何快速計(jì)算出兩個(gè)距離最近的點(diǎn)對(duì)？有兩個(gè)n*n的矩陣A，B，如何快速求解兩個(gè)矩陣的乘積分治算法思想的應(yīng)用是非常廣泛的，并不僅限于指導(dǎo)編程和算法設(shè)計(jì)。它還經(jīng)常用在海量數(shù)據(jù)處理的場(chǎng)景中。我們前面講的數(shù)據(jù)結(jié)構(gòu)和算法，大部分都是基于內(nèi)存和單機(jī)處理。但是，如果要處理的數(shù)據(jù)量非常大，沒法放到內(nèi)存中，這個(gè)時(shí)候，這些數(shù)據(jù)結(jié)構(gòu)和算法就無法工作了。比如，給10GB的訂單文件按照金額排序這樣一個(gè)需求，看似是一個(gè)簡單的排序問題，但是因?yàn)閿?shù)據(jù)量大，有10GB，而我們的機(jī)器的內(nèi)存可能只有2、3GB這樣子，無法要解決這種數(shù)據(jù)量大到內(nèi)存裝不下的問題，我們就可以利用分治的思想。我們可以將海量的數(shù)據(jù)集合根據(jù)某種方法，劃分為幾個(gè)小的數(shù)據(jù)集合，每個(gè)小的數(shù)據(jù)集合單獨(dú)加載到內(nèi)存來解決，然后再將小數(shù)據(jù)集合合并成大數(shù)據(jù)集合。實(shí)際上，利用這種分治的處理思路，不僅僅能克服內(nèi)存的限制，還能利用多線程或者多機(jī)處理，加快處理的速度。比如剛剛舉的那個(gè)例子，給10GB的訂單排序，我們就可以先掃描一遍訂單，根據(jù)訂單的金額，將10GB的文件劃分為幾個(gè)金額區(qū)間。比如訂單金額為1到100元的放到一個(gè)小文件，101到200之間的放到另一個(gè)文件，以此類推。這樣每個(gè)小文件都可以單獨(dú)加載到內(nèi)存排如果訂單數(shù)據(jù)在類似GFS這樣的分布式系統(tǒng)上，當(dāng)10GB的訂單被劃分成多個(gè)小文件的時(shí)候，每個(gè)文件可以并行加載到多臺(tái)機(jī)器上處理，最后再將結(jié)果合并在一起，這樣并行處理的速度也加快了很多。不過，這里有一個(gè)點(diǎn)要注意，就是數(shù)據(jù)的與計(jì)算所在的機(jī)器是同一個(gè)或者在網(wǎng)絡(luò)中靠的很近（比如一個(gè)局域網(wǎng)內(nèi)，數(shù)據(jù)存取速度很快），否則就會(huì)因?yàn)閿?shù)據(jù)的速度，導(dǎo)致整個(gè)處理過程不但不會(huì)變快，反而有可能變慢。MapReduce我們剛剛舉的訂單的例子，數(shù)據(jù)有10GB大小，可能給你的感受還不強(qiáng)烈。那如果我們要處理的數(shù)據(jù)是1T、10T、100T這樣子的，那一臺(tái)機(jī)器處理的效率肯定是非常低的。而對(duì)于谷歌搜索引擎來說，網(wǎng)頁爬取、、分析、分詞、計(jì)算權(quán)重、倒排索引等等各個(gè)環(huán)節(jié)中，實(shí)際上，MapReduce框架只是一個(gè)任務(wù)調(diào)度器，底層依賴GFS來數(shù)據(jù)，依賴管理機(jī)器。它從GFS中拿數(shù)據(jù)，交給Borg中的機(jī)器執(zhí)行，并且時(shí)刻機(jī)器執(zhí)行的進(jìn)度，一旦出現(xiàn)機(jī)器宕機(jī)、進(jìn)度卡殼等，就重新從Borg中調(diào)度一臺(tái)機(jī)器執(zhí)行。盡管MapReduce的模型非常簡單，但是在內(nèi)部應(yīng)用非常廣泛。它除了可以用來處理這種數(shù)據(jù)與數(shù)據(jù)之間存在關(guān)系的任務(wù)，比如MapReduce的經(jīng)典例子，統(tǒng)計(jì)文件中單億、上百億，如果單機(jī)處理，效率低下，我們就可以利用MapReduce提供的高可靠、高分治算法用概括就是“分而治之”，將原問題劃分成n個(gè)規(guī)模較小而結(jié)構(gòu)與原問題復(fù)雜度，另一個(gè)是解決海量數(shù)據(jù)處理問題。比如MapReduce本質(zhì)上就是利用了分治思我們也時(shí)常感嘆的創(chuàng)新能力如此之強(qiáng)，總是在引領(lǐng)技術(shù)的發(fā)展。實(shí)際上，創(chuàng)新并非離我們很遠(yuǎn)，創(chuàng)新的源泉來自對(duì)事物本質(zhì)的認(rèn)識(shí)。無數(shù)優(yōu)秀架構(gòu)設(shè)計(jì)的思想來源都是基礎(chǔ)的我們前面講過的數(shù)據(jù)結(jié)構(gòu)、算法、解決思路，以及舉的例子中，有哪些采用了分治算法的思想呢？除此之外，生活、工作中，還有沒有其他用到分治算法的地方呢？你可以自己回憶、總結(jié)一下，這對(duì)你將零散的知識(shí)提煉成體系非常有幫助。歡迎留言和我，也歡迎點(diǎn)擊“請(qǐng)朋友讀”，把今天的內(nèi)容給你的好友，和他一起討 不得售賣。頁面已增加防盜追蹤，將依法其上一 37|貪心算法：如何用貪心算法實(shí)現(xiàn)Huffman壓縮編碼下一 不定期福利第三期|測(cè)一測(cè)你的算法階段學(xué)習(xí)成言言Williamzh...置 三木 14淵 10GB劉遠(yuǎn) 然后求這兩塊之間點(diǎn)對(duì)的最小距離通過一些排序和刪除可以減少到6 6把歸并排序mergemerge(int[aintp,intq,intrmerge(int[]a,intlow,intmiddle,inthigh)更容易理解??，小細(xì)節(jié)，哈哈 代碼略有問題：1，numqi1)，應(yīng)該是在a[ia[jwhileiq)numqi1)，3ir-p+1而不是irpprivatevoidmerge(int[]a,intp,intq,intr) 3if(a[i]<=a[j])num+=(j-q-tmp[k++]=}elsetmp[k++]=劉文 2使用歸并排序求逆序度,實(shí)在是太妙了!老師的代碼一點(diǎn)兒問題都沒有,(j-q-1)記錄的是比Atmp放在下面的else里,可能需要再斟酌斟酌 … 1 leetcode 1劉 王老師，我覺得利用mrgesort找逆序?qū)€(gè)數(shù)的代碼，最后行，就是講tmp[]拷貝回[]這個(gè)操作，應(yīng)該是不需要的。在排序過，tp[]是有序的，a]是不變的。那么pa