我估計我不寫這樣的標題,吸引不了人氣。問題的起因是Javaeye的一個帖子《
淘寶面試題:如何充分利用多核CPU,計算很大的 List中所有整數的和》,看見為了這么個問題寫長長的Java代碼,讓我十分蛋疼。為了表示蛋定,我想介紹下用Clojure解決這個問題的方法。
題目很明確了,要你充分多核,這年頭不“多核”不好意思出去跟人打招呼,為了多核,你要將list拆分下,每個子list并發去計算和,然后綜合這些結果求出最終的和,您沒搞錯,這不是傳說中人見人愛的MapReduce嗎?你沒聽過?不好意思,你out了。
咱們先別著急并發,先搞個不并發的版本試試看,第一步,切分list,實在不好意思,clojure有現成的clojure.core/partition函數:
user=> (partition 3 3 [0] '(1 2 3 4 5 6 7 8 9 10))
((1 2 3) (4 5 6) (7 8 9) (10 0))
牛刀小試,將(1 2 3 4 5 6 7 8 9 10)切分成了3個子串,還有個可憐的犀利哥——10號同學沒辦法歸入任意一個組,只好讓他跟虛無的0為伴了。
partition的第三個參數指定一個湊伙的集合,當無法完全切分的時候,拿這個集合里的元素湊合。但是我們不能隨便湊合啊,隨便湊合加起來結果就不對了,用0就沒問題了。
切分完了,計算子集的和,那不要太簡單,該reduce同學上場,請大家歡呼、扔雞蛋,千萬別客氣:
user=> (reduce + 0 '(1 2 3))
6
自然要reduce,總要指定規則怎么reduce,我們這里很簡單,就是個加法運算,再給初始值0就好咯,reduce萬歲。
慢著,有個問題,
partition返回的是集合的集合((1 2 3) (4 5 6) (7 8 9) (10 0)),而上面的reduce卻要作用在子集里,怎么辦?無敵的map大神出場了,map的作用是將某個函數作用于集合上,并且返回作用后的集合結果,這里要干的事情就是將上面的reduce作用在partition返回的集合的集合上面:
user=> (map #(reduce + 0 % )(partition 3 3 [0] '(1 2 3 4 5 6 7 8 9 10)))
(6 15 24 10)
返回的是4個子集各自的和,答案肯定沒錯,最后一個結果不正是唯一的元素10嗎?這里可能比較費解的是#(reduce + 0 %),這其實定義了一個匿名函數,它接收一個參數,這個參數用百分號%默認指代,因為是將map作用于集合的集合,因此這里的%其實就是各個子集。
map返回的是個集合,又要求集合的總和,是不是又該reduce上場了?不好意思,map同學,這次演出你就一跑龍套的:
user=> (reduce + 0 (map #(reduce + 0 % )(partition 3 3 [0] '(1 2 3 4 5 6 7 8 9 10))))
55
偉大的55出來了,它不是一個人在戰斗,這一刻LISP、Scheme、Erlang、Scala、Clojure、JavaScript靈魂附體,它繼承了FP的光榮傳統,干凈漂亮地解決了這個問題。
綜合上面所述,我們給出一個非多核版本的解答:
(defn mysum [coll n]
(let [sub-colls (partition n n [0] coll)
result-coll (map #(reduce + 0 %) sub-colls) ]
(reduce + 0 result-coll)))
我們是使用了let語句綁定變量,純粹是為了更好看懂一些。sub-colls綁定到partition返回的集合的集合,result-coll就是各個子集的結果組成的集合,#(reduce + 0 %)是個匿名函數,其中%指向匿名函數的第一個參數,也就是每個子集。最終,利用reduce將result-coll的結果綜合在一起。
“我們要多核,我們要多核,我們不要西太平洋大學的野雞MapReduce"。
臺下別激動,神奇的“多核”馬上出場,我要改動的代碼只是那么一點點,用pmap替代map
(defn psum [coll n]
(let [sub-colls (partition n n [0] coll)
result-coll (pmap #(reduce + 0 %) sub-colls) ]
(reduce + 0 result-coll)))
完了嗎?真完了,你要改動的只有這么一點點,就可以讓切分出來的子集并發地計算了。(感謝網友@clojans的提醒)。
以下是原文:
首先是匿名函數改造一點點:
我干嘛了,我就加了個future,給你個未來。嚴肅點地說,future將啟動一個單獨的線程去reduce子集。現在result-coll里不再是直接的結果,而是各個子集的Future對象,為了得到真正的和,你需要等待線程結束并取得結果,因此最后的reduce也要小小地改動下:
(reduce #(+ %1 @%2) 0 result-coll))
reduce不再是簡單地用加號了,替代的則是一個兩個參數的匿名函數,第二個參數%2是Future對象,我們通過@操作符等待Future返回結果,并跟第一個參數%1(初始為0)作加法運算。
最終的多核版本:
(defn mysum2 [coll n]
(let [sub-colls (partition n n [0] coll)
result-coll (map #(future (reduce + 0 %)) sub-colls)]
(reduce #(+ %1 @%2) 0 result-coll)))
這個多核版本跟非多核版本區別大嗎?不大嗎?大嗎?不大嗎?……
可以看到,Clojure可以多么容易地在并發與非并發之間徘徊,習慣腳踏N只船了。