当前位置:天才代写 > tutorial > 其他教程 > 用R语言实现向量化与并行计较

用R语言实现向量化与并行计较

2017-12-04 08:00 星期一 所属: 其他教程 浏览:352

应用场景抉择常识的储蓄与东西的选择,反过来,无论你选择了什么样的东西,你必然会尽力地把它改革成切合本身应用场景所需的谁人样子。从这个原理来说,我选择了R作为数据挖掘人员手中攻城陷池的那把云梯,并尽力地把它改革本钱身但愿的谁人样子。

我最初打仗到专门用于科学计较的东西,是台甫鼎鼎的matlab,正如它辅佐了无数中国粹生顺利结业的赫赫功勋一样,它是我对付向量化计较的启蒙老师。用过matlab的人城市对其轮回布局的效率无法忍受,不知道是否有意而为之的这样的设计缺陷,迫使人们要想真正地用好它,就得接管它提供的向量化计较的思想,在把握了这个专门为高效计较而设计的计较思想之后,你会发明本身得到的不光是计较效率上的极大晋升,尚有算法设计思想上居高临下式的超过。

究竟matlab是更适合于研究规模的贸易软件,并且是闭源的,结业后不久,我就选择了R作为matlab的替代品,看中的正是R在向量化计较支持之余的机动性及富厚的第三方库,好像天生就是数据挖掘人员最趁手的那把刀。因为我需要的就是这样的一个计较情况,它不光是一门编程语言,也不必是一个已经很完备的东西。它就是这样的一个情况,拥有许多的各规模相关的东西包,我可以不必劳神太多过于底层的或与事情主题没有直接干系的问题,同时当不满足时我又具有对它最自由的掌控。实际上,我寻求的就是matlab与C之间的一个均衡点。R是一个面向科学工程计较出格是统计计较的东西,与matlab一样,其轮回布局的效率也无法让人满足,所以,我们必需操作向量化的编程范式,须要时回收并行/漫衍计较(因为,向量化本质上就是一种并行计较,也是我们凡是领略那种并行计较的天然先驱)。而这一切,在R眼前,都不是什么问题。

所谓向量化:

wikipedia中的界说是:Vectorization is the more limited process of converting a computer program from a Scalar implementation, which processes a single pair of operands at a time, to a vector implementation which processes one operation on multiple pairs of operands at once。向量化计较是一种非凡的并行计较的方法,对比于一般措施在同一时间只执行一个操纵的方法,它可以在同一时间执行多次操纵,凡是是对差异的数据执行同样的一个或一批指令,可能说把指令应用于一个数组/向量。

像R和matlab这样的现代科学软件包,城市以向量化作为其计较的根基特点(纵然python的numpy包也是如此),所以在R的根基运算中,到处可见向量化计较的影子,以下仅举几例,以让读者相识向量化是何等地简朴和直观:

向量取值:V[1:10]  (把get操纵应用于向量V的差异元素)

向量赋值:V[1:10] <- seq(1,10)  (把set操纵应用于一个序列与向量V的对应元素)

apply系列:lapply(V, mean)  (跟python的map函数雷同,是向量化最直接的表达形式)

矩阵运算:A + B;A %*% B  (矩阵的根基运算也是向量化的典范形式)

这些操纵很常见,乃至于我们都没有意识到这就是一种有助于提高计较机能的向量化计较,更忘了由此而把这样的思想扩展到我们算法设计的更多方面。纯熟利用它,你得到不光是计较上的长处,尚有对问题领略上的整体性。

向量化的处理惩罚方法是现代计较机的一个特点,无论硬件照旧软件上,都提供了支持。

硬件上的支持:Intel’s MMX, SSE, and ARM’s NEON instruction sets support such vectorized loops.(摘自wikipedia:http://en.wikipedia.org/wiki /Vectorization_(computer_science))

软件上的支持:著名的线性代数运算包blas对矩阵运算的自动并行化。譬喻,在R里执行如下的简朴呼吁,在不需要作任何特别事情的环境下,就可以自动地实现并行化(前提是你的呆板安装了blas)。

  M = matrix(5000*5000,5000, 5000) ## 生成一个5000*5000的矩阵
S = M %*% M ## 作矩阵乘法,在多核并安装了blas的呆板里,会自动并行

应用向量化的思维方法去办理问题:

当我们习惯了用C语言的单步轮回的思想来思考问题的时候,要把思维切换到向量化的方法是件较量坚苦的事件,以下显示一个例子,看用向量化的思想是怎么去办理问题,这样的描写又是何等美。

任务:对付稀疏矩阵M,让其第i(i=1…m)行的各非零元素减去某个值w[i]。

正常的轮回式思维的办理方案较量直观,作两层轮回,让第i行非零元素减去w[i]即可,但这样的操纵在剧本语言出格是像R这样的科学计较语言里执行效率不高,而当你面临的是一个稀疏矩阵时,问题又会变得巨大。

向量化的办理方案如下:

 

  ## 操作向量化的计较范式设计较法 
## 实例:稀疏矩阵差异行的各元素减去某个值   
library(Matrix)
generate <- function(nr, nc, sr){
L = nr*nc 
M = Matrix(data=0, nrow=nr, ncol=nc) 
idx = sample(1:L,as.integer(sr*L))
val = rnorm(sr*L, mean=1)
M[idx] = val 
return(M)
}

M = generate(10000,5000, 0.1)  ## 生成稀疏矩阵 
V = rnorm(10000)  ## 矩阵各行减去的值
N = M 
N@x = 1  ## 复制并配置矩阵 
A = Diagonal(nrow(N), V)%*% N  ## 把V的值放到新矩阵的各行非零单位中 
M@x = M@x- A@x  # M = M-A

撤除数据筹备阶段,真正用于办理问题的只有第16到19行的4行呼吁,十分短小精壮,但需要必然的线性代数常识去领略这个进程。

从向量化到并行计较:

除了计较机硬件与科学计较包的支持外,向量化计较照旧并行计较的天然先驱,假如你向量化后的算法效率仍然不佳,可以思量把它并行化。

R那浩如烟海的第三方包里提供了大量支持并行计较的包,这里选择的是snowfall这个包,它可以简朴地构建一个计较集群,把计较并行漫衍到集群的差异节点举办计较。以下通过一个例子较量轮回,向量化以及并行三种方法在效率上的差别。

实战案例:for轮回,apply,snowfall(并行)的较量。

任务:对一个矩阵每列排序并取回前10个。

  library(snowfall)  
mysort <- function(x){
  # replicate(2, sort(x))
   return(sort(x)[1:10])
}   

do_for <- function(M){
  ans = matrix(0,10, ncol(M))
  for(iin 1:ncol(M)){
    ans[,i]= sort(M)[1:10]  } 
}   

do_apply <- function(M){
  return(apply(M,2, mysort))
}   

do_snowfall <- function(M, ncl){
  sfInit(parallel=TRUE, cpus=ncl) ##初始化集群情况 
  ans <- sfApply(M,2, mysort) ##把任务分发到各个slave
  sfStop() ##封锁集群
  return(ans)
}   

#M = matrix(rnorm(10000000),100, 100000) 
#system.time(ans<- do_for(M))
#system.time(ans<- do_apply(M))
#system.time(ans<- do_snowfall(M,4)) ##用4个核并行

在我的处事器里运行的功效是这样的,do_for轮回根基不行用,do_apply可以在一分钟内运算完毕,而do_snowfall的时间为 do_apply的一半。当打消第4行的注释,即增加各个子任务的计较负荷后,do_apply与do_snowfall的计较时间都增加,而 do_snowfall的时间变为do_apply的三分之一。

结论1:向量化的计较方法比起传统的轮回计较有极大的机能优势。

结论2:由于并行的进程为:master把任务解析,分发到多个slave举办运算,slave返回功效到master。所以多核计较并不必然比最优的单核计较快,要看机能的瓶颈在slave照旧在master上。

结论3:适归并行/漫衍计较的情景主要有两种:一是各slave的计较淹灭为瓶颈,并行到多核能淘汰计较时间,越是slave耗时型的计较并行收益越大;二是一台呆板的内存不敷以举办整体的计较,漫衍到多台呆板计较能把内存占用分隔,这种环境下纵然漫衍计较比单机慢也是可以接管的。

与map-reduce扯扯干系:

Map-reduce是google三驾马车之一,试图把所有计较都转换为map和reduce两种根基的运算方法,而到达精采的可并行性,从而实现计较上的可扩展性。固然并不是每个公司都能实现像map-reduce那样的巨型计较框架,可是假如你能纯熟地利用向量化的思想设计你的算法,那其实就是一个map-reduce的超集。向量化计较这个编程范式比map-reduce要巨大,但本质上都是利用了两种根基的运算,假如你把apply想像为 map,把矩阵或矢量的乘运算想像为reduce,它们就是一体的。你总可以把向量化的计较通过apply和矩阵运算来实现,假如有一天你拥有了一个类 map-reduce的计较框架,按照它们的对应干系,你的算法迁移就会很是处所便,甚至,你可以在你已经实现的向量化算法集傍边抽取出一些共性来搭建本身的map-reduce系统。

别忘了一切优化的终极准则:过早的优化是妖怪。

并行计较或漫衍式计较是为数据量与计较劲日益膨胀的环境下所必需思量的,但它的逻辑布局与维护本钱也要高得多,假如你的应用场景还没到达需要举办并行可能漫衍计较的水平,没须要淌这趟混水。可是,向量化计较的编程范式却是很重要的,一个用向量化计较方法实现的算法,不单在其时得到了效益,并且其可扩展性也肯定是强悍的,因为正如前文所述,向量化计较就是并行计较的天然先驱。除此之外,常常用向量化的方法来思考你的问题,你必然能感觉到一种整体之美。

跋文:

以上内容是从我介入第三届中国R语言集会会议的讲稿中整理出来的,以讲向量化的思想为主,R语言为辅,其时的PPT可以从这里下载(PPT 上内容较量少,可以下载下来看备注部门)。我一直认为,通过这样的讲演,除了布道,更重要的是可以或许对本身一段时间以来的思考与事情做一个总结,其间无论是从自身整理照旧从他人的提问,本身从中都能有所收获。按照就地及过后一些听众的疑问,我后续整理了下面一些内容。

假如问题很难向量化怎么办:并不是说R中不能利用for式的轮回,事实上只有一层的for轮回,而且对机能没有太大的影响的话,是不需要作过多的优化的。假如是两层for轮回,可以思量用apply去掉一层,假如有三层的轮回,那很有大概就是你的算法有问题了。假如你的问题确实很难转换成向量化的形式,又可能说你已经懒于这样去做,那么不妨把最难于转换的一部门用C来实现,然后给R做一个接口,剩下的再思量向量化会简朴许多。我倡导的是团结R自有函数与向量化思想举办编程,因为R的自有函数大多都是用底层语言实现好的,效率有担保。

有人疑问是不是所有算法都可以并行:非根基的算法或多或少都是可以并行的,像kmeans,固然从整体来说是一个迭代依赖的非并行式算法,但在每一步的迭代中却是可以实施并行的。应用map-reduce框架基于这么一个假设,你的问题,总可以找到一种算法来实现,这种算法可以或大部门可以用map 加reduce根基操纵来实现。假如向量化能跟map-reduce对应起来,那么也可以认为,你的问题,总能找到一种可以用向量化思想暗示的算法来完全或部门办理,假如有些部门很难向量化,参考上一个问题。

我选择的算法自己就很巨大:有这么一个说法,假如你的数据不敷够多,信息不足完整,你会想出许多奇思怪招来从中得到结论,实际上许多科学上精良而巨大的算法是基于这种环境而设计出来的。而在实际中假如你的数据急剧膨胀,信息与噪声都足够地多,你的问题核心就变为如何用一个或一些简朴有效算法或算法的组合来提取有代价的信息。假如你在小数据集的时候习惯了回收巨大的算法,当你的应用场景转变了,数据局限变了,却仍旧沿用原有的思维方法,是注定要难过的(仅针对工程应用情况,而非科学应用情况)。

 原文链接:http://www.wentrue.net/blog/?p=945

 

    关键字:

天才代写-代写联系方式