對于比較復(fù)雜的互聯(lián)網(wǎng)應(yīng)用業(yè)務(wù)場景，比如海量數(shù)據(jù)商品搜索、廣告點(diǎn)擊算法、用戶行為挖掘、關(guān)聯(lián)推薦模型等等，由于數(shù)據(jù)量極大，對于數(shù)據(jù)處理的速度會要求非常高。要大幅提升算法的效率，最直接的方法就是：使用并行計算。

但是，并行計算有一個很大的問題：傳統(tǒng)的程序都是基于單機(jī)編寫的。要更改為多機(jī)并行的程序，需要耗費(fèi)較大的學(xué)習(xí)成本。尤其在真實(shí)的場景當(dāng)中，業(yè)務(wù)本身很復(fù)雜，初學(xué)者一頭扎進(jìn)去，容易繞暈了頭。

因此，我們需要一個通俗易懂的例子來直接看到并行計算的優(yōu)勢。

下面，淘寶網(wǎng)高級專家千峰就編寫了這樣的一個例子，51CTO受邀將這篇文章分享給大家。

文章概述

問題：

請寫一個程序，輸入M，然后打印出M個數(shù)字的所有排列組合（每個數(shù)字為1，2，3，4中的一個）。比如：M=3，輸出：

1，1，1
1，1，2
……
4，4，4

共64個

注意：這里是使用計算機(jī)遍歷出所有排列組合，而不是求總數(shù)，如果只求總數(shù)，可以直接利用數(shù)學(xué)公式進(jìn)行計算了。

傳統(tǒng)的單機(jī)解決方案：

1）單機(jī)遞歸

將n（1<=n<=4）看做深度，輸入的m看做廣度。當(dāng)m數(shù)字很大時，會超出單臺機(jī)器的計算局限導(dǎo)致緩慢。

2）單機(jī)迭代

求m個數(shù)字的排列組合，實(shí)際上都可以在m-1的結(jié)果基礎(chǔ)上得到。但是，當(dāng)m=14的時候，結(jié)果已經(jīng)上億了。無論以什么格式存，最終在單機(jī)上都會內(nèi)存溢出。

分布式并行計算解決方案：

1）多機(jī)遞歸

這是本篇文章的重點(diǎn)。

核心思想：重新設(shè)計算法，按多機(jī)進(jìn)行拆分和合并，利用并行計算優(yōu)勢去完成結(jié)果。

按照并行計算的算法，n臺計算機(jī)可以將遞歸降一級，n*n臺計算機(jī)可以將遞歸降兩級。理論上，只要機(jī)器足夠多，就能持續(xù)降低遞歸的復(fù)雜度。

運(yùn)行步驟：

使用fourinone框架設(shè)計分布式并行計算。整個框架通過一個ParkServerDemo做整體的工人注冊和分布式協(xié)調(diào)，中間有作為包工頭的CombCtor（分配工作+統(tǒng)計結(jié)果），最下面有多個CombWorker作為工人實(shí)現(xiàn)（干活兒+返回結(jié)果）。

文中有多機(jī)遞歸實(shí)現(xiàn)的完整代碼。

2）多機(jī)迭代

本文提供了三個多機(jī)迭代的思路。相對多機(jī)遞歸的方式，多機(jī)迭代的方式在這個例子中并不高效，因此沒有提出實(shí)現(xiàn)方式。

對這篇文章感興趣，可點(diǎn)擊這里查看全文