|
锁定老帖子 主题：几行代码解决淘宝面试题 之Clojure版
该帖已经被评为精华帖
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2010-07-16
chinpom 写道
ray_linn 写道
写了那么长，我们这也是map/reduce
var collection = Enumerable.Range(0, 1000000).ToArray<int>();
long total = 0;
Parallel.For<long>(0, collection.Length, () => 0, (j, loop, subtotal) =>
{
subtotal += collection[j];
return subtotal;
},
(x) => Interlocked.Add(ref total,x)
);
最简单的是：当然C#可以把所有魔术变成一行： collection.AsParallel<int>().Sum(); 比起楼主那些天书一样的语法，PLINQ简明到任何人一看就懂： 集合.并行处理.累加 上次还有人说，要处理大于10的，好吧，还是一行处理： collection.AsParallel<int>().Where(i=>i>10).Sum(); 集合.并行处理.取大于10的.累加。 至于什么partition之类的，本来就不需要程序员去介入，线程数应该等于CPU的core数目，手工去分partition，完全是浪费时间。 我有个问题，比如增加了一个额外的需求，想统计一下各个子线程分别花了多少时间来完成计算。你的的 C# 版代码容易修改吗？
|
| 返回顶楼 | |
|
发表时间：2010-07-16
dennis_zane 写道
chinpom 写道
我有个问
题，比如增加了一个额外的需求，想统计一下各个子线程分别花了多少时间来完成计算。楼主的 Clojure 版代码容易修改吗？
(defn mysum3 [coll n]
(let [sub-colls (partition n n [0] coll)
result-coll (map #(future (time (reduce + 0 %))) sub-colls)]
(reduce #(+ %1 @%2) 0 result-coll)))
1:1 user=> (mysum3 (range 0 1001) 400) "Elapsed time: 13.481042 msecs" "Elapsed time: 3.782884 msecs" "Elapsed time: 2.498223 msecs" 500500
javaeye不支持代码的高亮，折腾，注意time函数的位置。
楼主的代码可以适当简化了下。用pmap代替map,用partition-all代替partition,reduce 传入0也不是必须的。如下：
(user=> (defn mysum3 [coll n] (let [sub-colls (partition-all n coll)
result-coll (pmap #(time (reduce + %)) sub-colls)]
(reduce + result-coll)))
#'user/mysum3
user=> (mysum3 (range 0 1001) 400)
"Elapsed time: 0.223676 msecs"
"Elapsed time: 0.218443 msecs""
Elapsed time: 0.111362 msecs"
500500
|
| 返回顶楼 | |
|
发表时间：2010-07-16
最后修改：2010-07-16
Arbow 写道
import scala.actors.Futures._
object Test {
def split[T](part:Int, list:List[T], acc:List[List[T]]):List[List[T]] = {
if (list == Nil) return acc
val (head,tail) = list.splitAt(part)
split(part, tail, head :: acc)
}
def parallelSum(n:Int, list:List[Long]):Long = {
split(n,list,Nil).map({part=>future{part.sum}}).foldLeft(0l){_+_()}
}
def main(args : Array[String]) : Unit = {
val list = Range.Long(1, 10000000, 1).toList
val sum = parallelSum(list.size / 2, list)
}
}
使用了自带的Future库，split需自己写 
scala> (Range(0, 1001, 1) grouped 3 toList) .map(part=>future{part.sum}).foldLeft(0){_+_ ()}
res33: Int = 500500
|
| 返回顶楼 | |
|
发表时间：2010-07-16
IamSungod 写道
Arbow 写道
import scala.actors.Futures._
object Test {
def split[T](part:Int, list:List[T], acc:List[List[T]]):List[List[T]] = {
if (list == Nil) return acc
val (head,tail) = list.splitAt(part)
split(part, tail, head :: acc)
}
def parallelSum(n:Int, list:List[Long]):Long = {
split(n,list,Nil).map({part=>future{part.sum}}).foldLeft(0l){_+_()}
}
def main(args : Array[String]) : Unit = {
val list = Range.Long(1, 10000000, 1).toList
val sum = parallelSum(list.size / 2, list)
}
}
使用了自带的Future库，split需自己写
scala> (Range(0, 1001, 1) grouped 3 toList) .map({part=>future{part.sum}}).foldLeft(0){_+_ ()}
res33: Int = 500500
|
| 返回顶楼 | |
|
发表时间：2010-07-16
ray_linn 写道
IamSungod 写道
Arbow 写道
import scala.actors.Futures._
object Test {
def split[T](part:Int, list:List[T], acc:List[List[T]]):List[List[T]] = {
if (list == Nil) return acc
val (head,tail) = list.splitAt(part)
split(part, tail, head :: acc)
}
def parallelSum(n:Int, list:List[Long]):Long = {
split(n,list,Nil).map({part=>future{part.sum}}).foldLeft(0l){_+_()}
}
def main(args : Array[String]) : Unit = {
val list = Range.Long(1, 10000000, 1).toList
val sum = parallelSum(list.size / 2, list)
}
}
使用了自带的Future库，split需自己写
scala> (Range(0, 1001, 1) grouped 3 toList) .map({part=>future{part.sum}}).foldLeft(0){_+_ ()}
res33: Int = 500500
工厂方法future会起线程异步执行。也即每个分组的子列表，会并行地计算sum。
object Futures extends AnyRef
def future[T](body: ⇒ T): Future[T] |
| 返回顶楼 | |
|
发表时间：2010-07-16
准备找时间看看clojure，多谢楼主的文章。
|
| 返回顶楼 | |
|
发表时间：2010-07-17
Clojure 是什么东西？》
|
| 返回顶楼 | |
|
发表时间：2010-07-18
最后修改：2010-07-18
在将来的Scala中（scala2.8.1 or later）,可以用如下的代码实现：
val nums = ... //一个含数值的scala集合类 val sum = nums.par.sum //并行计算所有数值的和 当然，更一般性的形式应该是这样：
val nums = ... //一个含数值的scala集合类
val sum = nums.par.reduce{ (x,y) => x + y } //并行计算所有数值的和
|
| 返回顶楼 | |
|
发表时间：2010-07-18
测试了下，grouped() 方法是在 trait IterableLike 中定义的，无论对Array或List，在大容量下调用 grouped(n).toList，速度相当慢，推测是存在数据复制，严重影响加速比
比较好的方法是使用Array这种IndexedSeq存储测试数据，然后通过SeqView来作MapReduce，
def splitView[T](begin:Int, part:Int, list:IndexedSeq[T], acc:List[SeqView[T,IndexedSeq[T]]]):List[SeqView[T,IndexedSeq[T]]] = {
if (begin < list.size) splitView(begin+part, part, list, list.view(begin,begin+part) :: acc ) else acc
}
def parallelSum(n:Int, array:Array[Long]) = {
splitView(0,n,array,Nil).map({part=>future{part.sum}}).foldLeft(0l){_+_()}
}
|
| 返回顶楼 | |
|
发表时间：2010-07-18
Eastsun 写道 在将来的Scala中（scala2.8.1 or later）,可以用如下的代码实现：
val nums = ... //一个含数值的scala集合类 val sum = nums.par.sum //并行计算所有数值的和 当然，更一般性的形式应该是这样：
val nums = ... //一个含数值的scala集合类
val sum = nums.par.reduce{ (x,y) => x + y } //并行计算所有数值的和
这就是.NET里plinq的概念，scalar接受新东西比java快多了。 |
| 返回顶楼 | |
Arranges for the asynchronous execution of
body, returning a future representing the result.the computation to be carried out asynchronously
the future representing the result of the computation