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