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

    更新： 用pmap替代future函数。

 

    我估计我不写这样的标题，吸引不了人气。问题的起因是这个帖子《淘宝面试题：如何充分利用多核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"。

     台下别激动，神奇的“多核”马上出场，我要改动的代码只是那么一点点，将map替换成pmap就完了：

(defn psum [coll n]
     (let [sub-colls   (partition n n [0] coll)
           result-coll (pmap #(reduce + 0 %) sub-colls) ]
         (reduce + 0 result-coll)))

 

    完了吗？真的完了，这就是多核版本，每个切分出来的子集都将并发地reduce。感谢网友提醒，可以用pmap，我学clojure也才一个多星期 :D

 

    以下是原文：使用future对象。

 

     首先是匿名函数改造一点点：

#(future (reduce + 0 %)) 

 

    我干嘛了，我就加了个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只船了。

好是好, 不过是不是应该先来个clojure入门先, 或者用稍微普及一点的erlang/Ruby写一个?
热烈欢迎楼下出Eerlang版

Clojure是LISP的方言，如果对scheme之类有点了解的话，入门的门槛非常低，推荐个网上教程，比官方文档好很多

http://java.ociweb.com/mark/clojure/article.html

 

erlang、Ruby来写，也是很容易，用Clojure主要是Clojure本身就是基于java实现的，可以运行在jvm上，并且clojure的表达能力更简洁。

不错好文采 +1，
不过这篇文章有点曲高和寡了，毕竟Clojure的语法可以不算java语言范畴了（应该不算吧,如果Clojure算，Jython、JRuby也算吧），如果楼主用hadoop实现估计会有更多人参与讨论

虽然不会clojure  就冲lz的文采， 精华一个。

文采算法俱佳，楼主真乃神人也。

我觉得关键是要掌握原理，

我相信，用java也可以做出类似的函数，然后一行代码调用即可

蛋疼

没看懂啊。。。。
感觉实现原理上和计算机网络上的路由聚合原理非常相似，将数据份区间处理以提高并行性和效率。

LZ好神奇啊