應用場景決定知識的儲備與工具的選擇，反過來,，無論你選擇了什么樣的工具,，你一定會努力地把它改造成符合自己應用場景所需的那個樣子。從這個道理來說,，我選擇了R作為數(shù)據(jù)挖掘人員手中攻城陷池的那把云梯,，并努力地把它改造成自己希望的那個樣子。

我最初接觸到專門用于科學計算的工具,，是大名鼎鼎的matlab,，正如它幫助了無數(shù)中國學生順利畢業(yè)的赫赫功勞一樣，它是我對于向量化計算的啟蒙老師,。用過matlab的人都會對其循環(huán)結構的效率無法忍受,，不知道是否有意而為之的這樣的設計缺陷，迫使人們要想真正地用好它,，就得接受它提供的向量化計算的思想,，在掌握了這個專門為高效計算而設計的計算思想之后，你會發(fā)現(xiàn)自己獲得的不單是計算效率上的極大提升,，還有算法設計思想上高屋建瓴式的跨越,。

畢竟matlab是更適合于研究領域的商業(yè)軟件，而且是閉源的,，畢業(yè)后不久,，我就選擇了R作為matlab的替代品，看中的正是R在向量化計算支持之余的靈活性及豐富的第三方庫,，似乎天生就是數(shù)據(jù)挖掘人員最趁手的那把刀,。因為我需要的就是這樣的一個計算環(huán)境，它不單是一門編程語言,，也不必是一個已經很完備的工具,。它就是這樣的一個環(huán)境,，擁有很多的各領域相關的工具包，我可以不必操心太多過于底層的或與工作主題沒有直接關系的問題,，同時當不滿意時我又具有對它最自由的掌控,。實際上，我尋求的就是matlab與C之間的一個平衡點,。R是一個面向科學工程計算特別是統(tǒng)計計算的工具,，與matlab一樣，其循環(huán)結構的效率也無法讓人滿意,，所以,，我們必須利用向量化的編程范式，必要時采用并行/分布計算（因為,，向量化本質上就是一種并行計算,，也是我們通常理解那種并行計算的天然先驅）。而這一切,，在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,。向量化計算是一種特殊的并行計算的方式,，相比于一般程序在同一時間只執(zhí)行一個操作的方式，它可以在同一時間執(zhí)行多次操作,，通常是對不同的數(shù)據(jù)執(zhí)行同樣的一個或一批指令,，或者說把指令應用于一個數(shù)組/向量。

像R和matlab這樣的現(xiàn)代科學軟件包,，都會以向量化作為其計算的基本特點（即使python的numpy包也是如此）,，所以在R的基本運算中，隨處可見向量化計算的影子,，以下僅舉幾例,，以讓讀者了解向量化是多么地簡單和直觀：

向量取值：V[1:10]  （把get操作應用于向量V的不同元素）

向量賦值：V[1:10] <- seq(1,10)  （把set操作應用于一個序列與向量V的對應元素）

apply系列：lapply(V, mean)  （跟python的map函數(shù)類似，是向量化最直接的表達形式）

矩陣運算：A + B,；A %*% B  （矩陣的基本運算也是向量化的典型形式）

這些操作很常見,，以致于我們都沒有意識到這就是一種有助于提高計算性能的向量化計算，更忘了由此而把這樣的思想擴展到我們算法設計的更多方面,。熟練使用它,，你獲得不單是計算上的好處，還有對問題理解上的整體性,。

向量化的處理方式是現(xiàn)代計算機的一個特點,，無論硬件還是軟件上，都提供了支持,。

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

軟件上的支持：著名的線性代數(shù)運算包blas對矩陣運算的自動并行化,。例如,，在R里執(zhí)行如下的簡單命令，在不需要作任何額外工作的情況下,，就可以自動地實現(xiàn)并行化（前提是你的機器安裝了blas）,。

1
2

M = matrix(5000*5000, 5000, 5000)  ## 生成一個5000*5000的矩陣
S = M %*% M    ## 作矩陣乘法，在多核并安裝了blas的機器里,，會自動并行

應用向量化的思維方式去解決問題：

當我們習慣了用C語言的單步循環(huán)的思想來思考問題的時候,，要把思維切換到向量化的方式是件比較困難的事件，以下顯示一個例子,，看用向量化的思想是怎么去解決問題，這樣的描述又是多么美,。

任務：對于稀疏矩陣M,，讓其第i(i＝1…m)行的各非零元素減去某個值w[i]。

正常的循環(huán)式思維的解決方案比較直觀,，作兩層循環(huán),，讓第i行非零元素減去w[i]即可，但這樣的操作在腳本語言特別是像R這樣的科學計算語言里執(zhí)行效率不高,，而當你面對的是一個稀疏矩陣時,，問題又會變得復雜。

向量化的解決方案如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

## 利用向量化的計算范式設計算法
## 實例：稀疏矩陣不同行的各元素減去某個值
 
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

除去數(shù)據(jù)準備階段,，真正用于解決問題的只有第16到19行的4行命令,，十分短小精悍，但需要一定的線性代數(shù)知識去理解這個過程,。

從向量化到并行計算：

除了計算機硬件與科學計算包的支持外,，向量化計算還是并行計算的天然先驅，如果你向量化后的算法效率仍然不佳,，可以考慮把它并行化,。

R那浩如煙海的第三方包里提供了大量支持并行計算的包，這里選擇的是snowfall這個包,，它可以簡單地構建一個計算集群,，把計算并行分布到集群的不同節(jié)點進行計算。以下通過一個例子比較循環(huán),，向量化以及并行三種方式在效率上的差異,。

實戰(zhàn)案例：for循環(huán)，apply,，snowfall（并行）的比較,。

任務：對一個矩陣每列排序并取回前10個。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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(i in 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)  ##初始化集群環(huán)境
    ans <- sfApply(M, 2, mysort)  ##把任務分發(fā)到各個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循環(huán)基本不可用,，do_apply可以在一分鐘內運算完畢,，而do_snowfall的時間為do_apply的一半。當取消第4行的注釋,，即增加各個子任務的計算負荷后,，do_apply與do_snowfall的計算時間都增加，而do_snowfall的時間變?yōu)閐o_apply的三分之一,。

結論1：向量化的計算方式比起傳統(tǒng)的循環(huán)計算有極大的性能優(yōu)勢,。

結論2：由于并行的過程為：master把任務分解，分發(fā)到多個slave進行運算,，slave返回結果到master,。所以多核計算并不一定比最優(yōu)的單核計算快，要看性能的瓶頸在slave還是在master上,。

結論3：適合并行/分布計算的情景主要有兩種：一是各slave的計算耗費為瓶頸,，并行到多核能減少計算時間，越是slave耗時型的計算并行收益越大,；二是一臺機器的內存不足以進行整體的計算,，分布到多臺機器計算能把內存占用分開，這種情況下即使分布計算比單機慢也是可以接受的,。

與map-reduce扯扯關系：

Map-reduce是google三駕馬車之一,，試圖把所有計算都轉換為map和reduce兩種基本的運算方式，而達到良好的可并行性,，從而實現(xiàn)計算上的可擴展性,。雖然并不是每個公司都能實現(xiàn)像map-reduce那樣的巨型計算框架，但是如果你能熟練地使用向量化的思想設計你的算法,，那其實就是一個map-reduce的超集,。向量化計算這個編程范式比map-reduce要復雜，但本質上都是使用了兩種基本的運算,，如果你把apply想像為map,，把矩陣或矢量的乘運算想像為reduce，它們就是一體的,。你總可以把向量化的計算通過apply和矩陣運算來實現(xiàn),，如果有一天你擁有了一個類map-reduce的計算框架，根據(jù)它們的對應關系,，你的算法遷移就會非常地方便,，甚至，你可以在你已經實現(xiàn)的向量化算法集當中抽取出一些共性來搭建自己的map-reduce系統(tǒng),。

別忘了一切優(yōu)化的終極準則：過早的優(yōu)化是魔鬼,。

并行計算或分布式計算是為數(shù)據(jù)量與計算量日益膨脹的情況下所必須考慮的，但它的邏輯結構與維護成本也要高得多，如果你的應用場景還沒達到需要進行并行或者分布計算的程度,，沒必要淌這趟混水,。但是，向量化計算的編程范式卻是很重要的,，一個用向量化計算方式實現(xiàn)的算法,，不但在當時獲得了效益，而且其可擴展性也必定是強悍的,，因為正如前文所述,，向量化計算就是并行計算的天然先驅。除此之外,，經常用向量化的方式來思考你的問題,，你一定能感受到一種整體之美。

后記：

以上內容是從我參加第三屆中國R語言會議的講稿中整理出來的,，以講向量化的思想為主,，R語言為輔，當時的PPT可以從這里下載（PPT上內容比較少,，可以下載下來看備注部分）。我一直認為,，通過這樣的講演,，除了布道，更重要的是能夠對自己一段時間以來的思考與工作做一個總結,，其間無論是從自身整理還是從他人的提問,，自己從中都能有所收獲。根據(jù)當場及事后一些聽眾的疑問,，我后續(xù)整理了下面一些內容,。

如果問題很難向量化怎么辦：并不是說R中不能使用for式的循環(huán)，事實上只有一層的for循環(huán),，并且對性能沒有太大的影響的話,，是不需要作過多的優(yōu)化的。如果是兩層for循環(huán),，可以考慮用apply去掉一層,，如果有三層的循環(huán)，那很有可能就是你的算法有問題了,。如果你的問題確實很難轉換成向量化的形式,，又或者說你已經懶于這樣去做，那么不妨把最難于轉換的一部分用C來實現(xiàn),，然后給R做一個接口,，剩下的再考慮向量化會簡單很多。我提倡的是結合R自有函數(shù)與向量化思想進行編程，因為R的自有函數(shù)大多都是用底層語言實現(xiàn)好的,，效率有保證,。

有人疑問是不是所有算法都可以并行：非基本的算法或多或少都是可以并行的，像kmeans,，雖然從整體來說是一個迭代依賴的非并行式算法,，但在每一步的迭代中卻是可以實施并行的。應用map-reduce框架基于這么一個假設,，你的問題,，總可以找到一種算法來實現(xiàn)，這種算法可以或大部分可以用map加reduce基本操作來實現(xiàn),。如果向量化能跟map-reduce對應起來,，那么也可以認為，你的問題,，總能找到一種可以用向量化思想表示的算法來完全或部分解決,，如果有些部分很難向量化，參考上一個問題,。

我選擇的算法本身就很復雜：有這么一個說法,，如果你的數(shù)據(jù)不足夠多，信息不夠完整,，你會想出很多奇思怪招來從中獲得結論,，實際上很多科學上精巧而復雜的算法是基于這種情況而設計出來的。而在實際中如果你的數(shù)據(jù)急劇膨脹,，信息與噪聲都足夠地多,，你的問題焦點就變?yōu)槿绾斡靡粋€或一些簡單有效算法或算法的組合來提取有價值的信息。如果你在小數(shù)據(jù)集的時候習慣了采用復雜的算法,，當你的應用場景轉變了,，數(shù)據(jù)規(guī)模變了，卻仍舊沿用原有的思維方式,，是注定要尷尬的（僅針對工程應用環(huán)境,，而非科學應用環(huán)境）。