几行代码解决淘宝面试题之Clojure版
2023-03-14 10:32:00 时间
我估计我不写这样的标题,吸引不了人气。问题的起因是Javaeye的一个帖子《淘宝面试题:如何充分利用多核CPU,计算很大的 List中所有整数的和》,看见为了这么个问题写长长的Java代码,让我十分蛋疼。为了表示蛋定,我想介绍下用Clojure解决这个问题的方法。
题目很明确了,要你充分多核,这年头不“多核”不好意思出去跟人打招呼,为了多核,你要将list拆分下,每个子list并发去计算和,然后综合这些结果求出最终的和,您没搞错,这不是传说中人见人爱的MapReduce吗?你没听过?不好意思,你out了。
咱们先别着急并发,先搞个不并发的版本试试看,第一步,切分list,实在不好意思,clojure有现成的clojure.core/partition函数:
牛刀小试,将(1 2 3 4 5 6 7 8 9 10)切分成了3个子串,还有个可怜的犀利哥——10号同学没办法归入任意一个组,只好让他跟虚无的0为伴了。partition的第三个参数指定一个凑伙的集合,当无法完全切分的时候,拿这个集合里的元素凑合。但是我们不能随便凑合啊,随便凑合加起来结果就不对了,用0就没问题了。
切分完了,计算子集的和,那不要太简单,该reduce同学上场,请大家欢呼、扔鸡蛋,千万别客气:
自然要reduce,总要指定规则怎么reduce,我们这里很简单,就是个加法运算,再给初始值0就好咯,reduce万岁。
慢着,有个问题,partition返回的是集合的集合((1 2 3) (4 5 6) (7 8 9) (10 0)),而上面的reduce却要作用在子集里,怎么办?无敌的map大神出场了,map的作用是将某个函数作用于集合上,并且返回作用后的集合结果,这里要干的事情就是将上面的reduce作用在partition返回的集合的集合上面:
返回的是4个子集各自的和,答案肯定没错,最后一个结果不正是唯一的元素10吗?这里可能比较费解的是#(reduce + 0 %),这其实定义了一个匿名函数,它接收一个参数,这个参数用百分号%默认指代,因为是将map作用于集合的集合,因此这里的%其实就是各个子集。
map返回的是个集合,又要求集合的总和,是不是又该reduce上场了?不好意思,map同学,这次演出你就一跑龙套的:
伟大的55出来了,它不是一个人在战斗,这一刻LISP、Scheme、Erlang、Scala、Clojure、JavaScript灵魂附体,它继承了FP的光荣传统,干净漂亮地解决了这个问题。
综合上面所述,我们给出一个非多核版本的解答:
我们是使用了let语句绑定变量,纯粹是为了更好看懂一些。sub-colls绑定到partition返回的集合的集合,result-coll就是各个子集的结果组成的集合,#(reduce + 0 %)是个匿名函数,其中%指向匿名函数的第一个参数,也就是每个子集。最终,利用reduce将result-coll的结果综合在一起。
“我们要多核,我们要多核,我们不要西太平洋大学的野鸡MapReduce"。
台下别激动,神奇的“多核”马上出场,我要改动的代码只是那么一点点,用pmap替代map
完了吗?真完了,你要改动的只有这么一点点,就可以让切分出来的子集并发地计算了。(感谢网友@clojans的提醒)。
以下是原文:
首先是匿名函数改造一点点:
我干嘛了,我就加了个future,给你个未来。严肃点地说,future将启动一个单独的线程去reduce子集。现在result-coll里不再是直接的结果,而是各个子集的Future对象,为了得到真正的和,你需要等待线程结束并取得结果,因此最后的reduce也要小小地改动下:
reduce不再是简单地用加号了,替代的则是一个两个参数的匿名函数,第二个参数%2是Future对象,我们通过@操作符等待Future返回结果,并跟第一个参数%1(初始为0)作加法运算。
最终的多核版本:
题目很明确了,要你充分多核,这年头不“多核”不好意思出去跟人打招呼,为了多核,你要将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 0))
牛刀小试,将(1 2 3 4 5 6 7 8 9 10)切分成了3个子串,还有个可怜的犀利哥——10号同学没办法归入任意一个组,只好让他跟虚无的0为伴了。partition的第三个参数指定一个凑伙的集合,当无法完全切分的时候,拿这个集合里的元素凑合。但是我们不能随便凑合啊,随便凑合加起来结果就不对了,用0就没问题了。
切分完了,计算子集的和,那不要太简单,该reduce同学上场,请大家欢呼、扔鸡蛋,千万别客气:
user=> (reduce + 0 '(1 2 3))
6
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)
(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
伟大的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 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)))
(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 @%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)))
(let [sub-colls (partition n n [0] coll)
result-coll (map #(future (reduce + 0 %)) sub-colls)]
(reduce #(+ %1 @%2) 0 result-coll)))
这个多核版本跟非多核版本区别大吗?不大吗?大吗?不大吗?……
可以看到,Clojure可以多么容易地在并发与非并发之间徘徊,习惯脚踏N只船了。
文章转自庄周梦蝶 ,原文发布时间 2010-07-15
相关文章
- 使用 Amazon Redshift 通过配额机制监控及控制 schema 存储空间
- Amazon EMR Managed Scaling 介绍——自动调整集群大小,高效节约运营成本
- Amazon Redshift Federated Query 最佳实践
- 如何在 ADFS 与 AWS 之间建立信任,并通过 Active Directory 凭证配合 ODBC 驱动程序接入 Amazon Athena
- 在EMR 6.0.0 中使用 Docker 简化您的 Spark 依赖项管理
- Komodo Health 公司如何在 EKS 与 EMR 6 上使用多租户 Notebook 平台建立自助服务分析方案
- Compass 公司使用 Amazon ES 推动房屋搜索流程的简化与现代化
- AWS Wavelength 区现已在波士顿和旧金山开放
- Alexa 使用 Amazon Translate 覆盖更多国际客户
- 使用 Amazon Kendra 强化企业搜索能力
- New – Using Amazon GuardDuty to Protect Your S3 Buckets
- Java ThreadLocal详解
- 云财务管理落户 AWS 中国
- Amazon Translate 现在支持 Office 文档
- Amazon Fraud Detector 现已全面推出
- AWS DataSync 新增本地对象存储支持
- 新增功能 – 基于 AWS Graviton2 的 Amazon EC2 实例,支持本地基于 NVMe 的 SSD 存储
- 借助 NetApp CVO 实现 EDA 混合架构下的统一数据存储
- 使用分布式可用性组实现多区域 SQL Server 部署
- Amazon Kinesis Data Analytics 无服务器流式数据处理服务简介