庄周梦蝶

生活、程序、未来
   :: 首页 ::  ::  :: 聚合  :: 管理

几行代码解决淘宝面试题之Clojure版

Posted on 2010-07-15 11:19 dennis 阅读(7880) 评论(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实在太强大了...

只有注册用户登录后才能发表评论。


网站导航: