莊周夢(mèng)蝶

          生活、程序、未來(lái)
             :: 首頁(yè) ::  ::  :: 聚合  :: 管理

          幾行代碼解決淘寶面試題之Clojure版

          Posted on 2010-07-15 11:19 dennis 閱讀(8097) 評(píng)論(10)  編輯  收藏 所屬分類(lèi): java 、Clojure
              我估計(jì)我不寫(xiě)這樣的標(biāo)題,吸引不了人氣。問(wèn)題的起因是Javaeye的一個(gè)帖子《淘寶面試題:如何充分利用多核CPU,計(jì)算很大的 List中所有整數(shù)的和》,看見(jiàn)為了這么個(gè)問(wèn)題寫(xiě)長(zhǎng)長(zhǎng)的Java代碼,讓我十分蛋疼。為了表示蛋定,我想介紹下用Clojure解決這個(gè)問(wèn)題的方法。

              題目很明確了,要你充分多核,這年頭不“多核”不好意思出去跟人打招呼,為了多核,你要將list拆分下,每個(gè)子list并發(fā)去計(jì)算和,然后綜合這些結(jié)果求出最終的和,您沒(méi)搞錯(cuò),這不是傳說(shuō)中人見(jiàn)人愛(ài)的MapReduce嗎?你沒(méi)聽(tīng)過(guò)?不好意思,你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)切分成了3個(gè)子串,還有個(gè)可憐的犀利哥——10號(hào)同學(xué)沒(méi)辦法歸入任意一個(gè)組,只好讓他跟虛無(wú)的0為伴了。partition的第三個(gè)參數(shù)指定一個(gè)湊伙的集合,當(dāng)無(wú)法完全切分的時(shí)候,拿這個(gè)集合里的元素湊合。但是我們不能隨便湊合啊,隨便湊合加起來(lái)結(jié)果就不對(duì)了,用0就沒(méi)問(wèn)題了。

             切分完了,計(jì)算子集的和,那不要太簡(jiǎn)單,該reduce同學(xué)上場(chǎng),請(qǐng)大家歡呼、扔雞蛋,千萬(wàn)別客氣:
          user=> (reduce + 0 '(1 2 3))
          6
            
              自然要reduce,總要指定規(guī)則怎么reduce,我們這里很簡(jiǎn)單,就是個(gè)加法運(yùn)算,再給初始值0就好咯,reduce萬(wàn)歲。

              慢著,有個(gè)問(wèn)題,partition返回的是集合的集合((1 2 3) (4 5 6) (7 8 9) (10 0)),而上面的reduce卻要作用在子集里,怎么辦?無(wú)敵的map大神出場(chǎng)了,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)

              返回的是4個(gè)子集各自的和,答案肯定沒(méi)錯(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上場(chǎng)了?不好意思,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出來(lái)了,它不是一個(gè)人在戰(zhàn)斗,這一刻LISP、Scheme、Erlang、Scala、Clojure、JavaScript靈魂附體,它繼承了FP的光榮傳統(tǒng),干凈漂亮地解決了這個(gè)問(wèn)題。

              綜合上面所述,我們給出一個(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語(yǔ)句綁定變量,純粹是為了更好看懂一些。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),神奇的“多核”馬上出場(chǎ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)))

             完了嗎?真完了,你要改動(dòng)的只有這么一點(diǎn)點(diǎn),就可以讓切分出來(lái)的子集并發(fā)地計(jì)算了。(感謝網(wǎng)友@clojans的提醒)。

          以下是原文:
              首先是匿名函數(shù)改造一點(diǎn)點(diǎn):
              我干嘛了,我就加了個(gè)future,給你個(gè)未來(lái)。嚴(yán)肅點(diǎn)地說(shuō),future將啟動(dòng)一個(gè)單獨(dú)的線程去reduce子集。現(xiàn)在result-coll里不再是直接的結(jié)果,而是各個(gè)子集的Future對(duì)象,為了得到真正的和,你需要等待線程結(jié)束并取得結(jié)果,因此最后的reduce也要小小地改動(dòng)下:
          (reduce #(+ %1 @%20 result-coll))

              reduce不再是簡(jiǎn)單地用加號(hào)了,替代的則是一個(gè)兩個(gè)參數(shù)的匿名函數(shù),第二個(gè)參數(shù)%2是Future對(duì)象,我們通過(guò)@操作符等待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 @%20 result-coll)))

             這個(gè)多核版本跟非多核版本區(qū)別大嗎?不大嗎?大嗎?不大嗎?……
             可以看到,Clojure可以多么容易地在并發(fā)與非并發(fā)之間徘徊,習(xí)慣腳踏N只船了。


             

          評(píng)論

          # re: 幾行代碼解決淘寶面試題之Clojure版[未登錄](méi)  回復(fù)  更多評(píng)論   

          2010-07-15 13:24 by 楊一
          我真的很擔(dān)心FP太強(qiáng)大了最后變成matlab

          # re: 幾行代碼解決淘寶面試題之Clojure版[未登錄](méi)  回復(fù)  更多評(píng)論   

          2010-07-15 14:06 by k
          蛋疼

          # re: 幾行代碼解決淘寶面試題之Clojure版  回復(fù)  更多評(píng)論   

          2010-07-15 15:55 by subnet
          威~~~武~~~!

          請(qǐng)問(wèn)能否做下性能對(duì)比?

          # re: 幾行代碼解決淘寶面試題之Clojure版  回復(fù)  更多評(píng)論   

          2010-07-16 09:20 by t
          語(yǔ)法真難看

          # re: 幾行代碼解決淘寶面試題之Clojure版  回復(fù)  更多評(píng)論   

          2010-07-16 13:38 by clojans
          直接使用pmap不就ok了嗎?

          # re: 幾行代碼解決淘寶面試題之Clojure版  回復(fù)  更多評(píng)論   

          2010-07-16 13:57 by dennis
          @clojans
          嗯,用pmap更簡(jiǎn)單,我沒(méi)有想到,不好意思,接觸clojure才一個(gè)多星期。

          # re: 幾行代碼解決淘寶面試題之Clojure版[未登錄](méi)  回復(fù)  更多評(píng)論   

          2011-01-18 22:46 by feng
          clojure 確實(shí)很強(qiáng)大,亦學(xué)習(xí)clojure中。

          # re: 幾行代碼解決淘寶面試題之Clojure版  回復(fù)  更多評(píng)論   

          2013-08-23 23:06 by e3rp4y
          (reduce + 0 '(1 2 3)) => (apply + '(1 2 3))

          # re: 幾行代碼解決淘寶面試題之Clojure版  回復(fù)  更多評(píng)論   

          2013-09-27 20:34 by paomian
          @t
          哪里難看了?習(xí)慣問(wèn)題

          # re: 幾行代碼解決淘寶面試題之Clojure版  回復(fù)  更多評(píng)論   

          2015-12-16 15:19 by gjl
          clojure實(shí)在太強(qiáng)大了...
          主站蜘蛛池模板: 台江县| 米林县| 台安县| 礼泉县| 太仓市| 浦县| 田阳县| 腾冲县| 凤冈县| 昭平县| 双鸭山市| 葫芦岛市| 正宁县| 工布江达县| 廉江市| 邵武市| 宜宾县| 寿阳县| 普格县| 介休市| 汤原县| 漾濞| 绍兴市| 澄江县| 定结县| 珲春市| 孟津县| 咸阳市| 南投县| 东乡族自治县| 商丘市| 双牌县| 延长县| 电白县| 大余县| 屏东县| 丹棱县| 荆门市| 泗水县| 都昌县| 长春市|