<rt id="bn8ez"></rt>
<label id="bn8ez"></label>

  • <span id="bn8ez"></span>

    <label id="bn8ez"><meter id="bn8ez"></meter></label>

    莊周夢蝶

    生活、程序、未來
       :: 首頁 ::  ::  :: 聚合  :: 管理

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

    Posted on 2010-07-15 11:19 dennis 閱讀(8095) 評論(10)  編輯  收藏 所屬分類: javaClojure
        我估計我不寫這樣的標題,吸引不了人氣。問題的起因是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 @%20 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 @%20 result-coll)))

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


       

    評論

    # re: 幾行代碼解決淘寶面試題之Clojure版[未登錄]  回復  更多評論   

    2010-07-15 13:24 by 楊一
    我真的很擔心FP太強大了最后變成matlab

    # re: 幾行代碼解決淘寶面試題之Clojure版[未登錄]  回復  更多評論   

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

    # re: 幾行代碼解決淘寶面試題之Clojure版  回復  更多評論   

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

    請問能否做下性能對比?

    # re: 幾行代碼解決淘寶面試題之Clojure版  回復  更多評論   

    2010-07-16 09:20 by t
    語法真難看

    # re: 幾行代碼解決淘寶面試題之Clojure版  回復  更多評論   

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

    # re: 幾行代碼解決淘寶面試題之Clojure版  回復  更多評論   

    2010-07-16 13:57 by dennis
    @clojans
    嗯,用pmap更簡單,我沒有想到,不好意思,接觸clojure才一個多星期。

    # re: 幾行代碼解決淘寶面試題之Clojure版[未登錄]  回復  更多評論   

    2011-01-18 22:46 by feng
    clojure 確實很強大,亦學習clojure中。

    # re: 幾行代碼解決淘寶面試題之Clojure版  回復  更多評論   

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

    # re: 幾行代碼解決淘寶面試題之Clojure版  回復  更多評論   

    2013-09-27 20:34 by paomian
    @t
    哪里難看了?習慣問題

    # re: 幾行代碼解決淘寶面試題之Clojure版  回復  更多評論   

    2015-12-16 15:19 by gjl
    clojure實在太強大了...
    主站蜘蛛池模板: 久久狠狠躁免费观看2020| 亚洲成AV人片高潮喷水| 成人免费av一区二区三区| 亚洲XX00视频| 九九久久精品国产免费看小说| 国产一区二区视频免费| 男女超爽视频免费播放| 日韩精品电影一区亚洲| 特级一级毛片免费看| 国产精品亚洲mnbav网站 | 国产AV无码专区亚洲AV手机麻豆| 精品日韩亚洲AV无码| 污污网站免费观看| 久久亚洲sm情趣捆绑调教| 3344永久在线观看视频免费首页| 精品亚洲成a人片在线观看| 91免费在线播放| 国产人成免费视频| 日本特黄特色AAA大片免费| 亚洲精品视频免费观看| 中文字幕高清免费不卡视频| 亚洲AV无码专区国产乱码4SE| 无码成A毛片免费| 亚洲综合在线成人一区| 青青在线久青草免费观看| 亚洲第一综合天堂另类专| 免费人妻av无码专区| 一区二区在线视频免费观看| 亚洲AV成人一区二区三区AV| 久草在视频免费福利| 国产亚洲精品美女久久久久| 亚洲精品亚洲人成在线观看| 91精品国产免费久久国语蜜臀| 亚洲国产成人无码av在线播放| 日本免费电影一区| 91国内免费在线视频| 亚洲国产韩国一区二区| 国产三级免费电影| 91精品视频在线免费观看| 亚洲一线产品二线产品| 久久久久亚洲av成人无码电影|