其實一直想討論這個議題，只是遲遲沒有去寫這個
這次就想說來分享一下preallocated memory這件事
很多人會寫這樣的code:
A_list = list()
for (i in 1:N){
A_list[[i]] = # give something
}
會直接給一個空的list然後開始塞東西
R裡面的list其實是一群pointer組成的向量
如果你沒有聽過pointer
你可當做"指示物"去引導到你要的東西
舉例來說：
List_1 <- list(a = 1:5, b = 2:4)
List_1就含有兩個pointer，指向a跟b的儲存位置
我們可以從tracemem來看到這點
tracemem回傳一個物件儲存在記憶體的位置
你可以透過這個去看物件有在記憶中被複製或被搬移等動作
我們來print out List_1的memory位置
cat(tracemem(List_1), '\n')
## <0000000015083EA8>
cat(tracemem(List_1[[1]]), '\n')
## <00000000060E97F0>
cat(tracemem(List_1[[2]]), '\n')
## <0000000015083EE0>
這樣可以看出tracemem(List_1)跟tracemem(List_1[[1]])的位置不同
如果list是沿著物件的大小去儲存
那麼我們應該看到List_1的位置跟List_1[[1]]的位置是重疊的
但是這裡顯示並非如此，因此，我們可以合理推斷
list是一群pointer組成的向量
以上如果你學過C++，應該對這個部分比較熟悉
如果不太熟悉，記得這個結果：list是一群pointer的向量
接著我們看如果我們給一個空的list
去做擴充list的動作會發生什麼事情
s1 = list()
cat(tracemem(s1), '\n')
## <000000001523AB70>
for (i in 1:3)
{
s1[[i]] = rnorm(i)
cat(tracemem(s1), '\n')
}
## <00000000061DAC48>
## <00000000067A55C8>
## <000000000AC68AE8>
這裡我們可以看到s1的位置不斷的被改變
代表說s1其實不斷搬移到不同位置上
那我們看看如果我們先設定好list大小的結果
s2 = vector('list', 3)
cat(tracemem(s2), '\n')
<000000000AD48B58>
for (i in 1:3)
{
s2[[i]] = rnorm(i)
cat(tracemem(s2), '\n')
cat(tracemem(s2[[i]]), '\n')
}
## <000000000AD48B58>
## <000000000AD48B58>
## <000000000AD48B58>
我們可以看到完全沒有改變s2的位置，而s2沒有被搬移過
那麼沒有搬移告訴我們什麼事情？
沒有搬移就告訴我們不需要把位置上的東西做複製
不用做複製，那麼我們的操作就不會因為複製而變慢
我提供一個簡單的測試去測試有無preallocated memory的迴圈速度差異
f_without_preallocated <- function(){
a <- list()
for (i in 1:1e6){ a[[i]] <- rnorm(10) }
}
f_with_preallocated <- function(){
a <- vector('list', 1e6)
for (i in 1:1e6){ a[[i]] <- rnorm(10) }
}
library(rbenchmark)
benchmark(f_without_preallocated(), f_with_preallocated(),
columns = c("test", "replications", "elapsed", "relative"),
order = "relative", replications = 20)
## test replications elapsed relative
## 2 f_with_preallocated() 20 5.92 1.000
## 1 f_without_preallocated() 20 360.90 60.963
可以看到差到快60倍的速度，因此，建議preallocate memory!!
我的環境：windows 7 64bit, RRO-3.2.0 (2015-04-16), i7-3770K@4.4GHz
list只是其中一個例子
我只是挑大家最常用到的case去做
還有一些案例像是：
MaxIter = 1e6
x = c()
i = 0
while (iter < MaxIter){
i <- i + 1
x <- c(x, i)
if (## some condition)
break
}
這種不斷增長vector x的方式也是十分的消耗記憶體複製的時間
這種不知道長度時最多人用的做法
但是其實可以換成下列這樣：
MaxIter = 1e6
x = rep(NA_real_, 10)
for (i in 1:MaxIter)
x[i] <- i
if (## some condition)
break
}
x = x[!is.na(x)]
再給一個簡單的benchmark：
f_while_1 <- function(){
MaxIter = 1e5
x = c()
i = 0
while (iter < MaxIter){
i <- i + 1
x <- c(x, i)
if (i > 5e4)
break
}
x
}
f_while_2 <- function(){
MaxIter = 1e5
x = rep(NA_real_, MaxIter) ## 註一
for (i in 1:MaxIter)
x[i] <- i
if (i > 5e4)
break
}
(x = x[!is.na(x)])
}
library(rbenchmark)
benchmark(f_while_1(), f_while_2(),
columns = c("test", "replications", "elapsed", "relative"),
order = "relative", replications = 20)
## test replications elapsed relative
## 2 f_while_2() 20 1.00 1.00
## 1 f_while_1() 20 53.17 53.17
可以看出平均消耗的時間可以差到53倍。
這些測試希望可以帶給大家一些東西，謝謝觀看此篇文章。
裡面還有一些操作的議題，像是向量化運算(vectorise)等，有機會再來討論
有興趣可以先去讀讀看R in a Nutshell第24章有提到相關的事情
(詳細資訊：R in a Nutshell, Joseph Adler, O'Reilly)
註一：NA有四種類型NA_integer_, NA_real_, NA_complex_ and NA_character_
分別是整數、帶小數的數、複數跟字元的NA類別
不同NA類別會給vector不同類型的儲存大小、儲存類型
給一個適當的NA也是一個好方法
另外，一般的NA是NA_character_
PS：
有些人會提到sapply, lapply會比較有效率：
但是其實sapply跟lapply只是有preallocate memory的動作
(sapply, lapply可能有其他優化，如果有人知道再麻煩告知我)
會比沒有preallocate memory的for-loop快而已
在你要同時進行多個list或是向量操作
還是建議用迴圈比較簡單做操作，因為時間根本不會差太多
在一些情況下，sapply跟lapply會更慢 (註二)
給一個簡單的例子：
N = 5e4
st <- proc.time()
a11 <- c()
a21 <- list()
a31 <- c()
for (i in 1:N){
a11[i] <- i
a21[[i]] <- cumsum(1:i)
a31[i] <- sum(1:i)
}
proc.time() - st
## user system elapsed
## 12.70 0.02 12.75
st <- proc.time()
a12 <- sapply(1:N, function(i)i)
a22 <- lapply(1:N, function(i) cumsum(1:i))
a32 <- lapply(1:N, function(i) sum(1:i))
proc.time() - st
## user system elapsed
## 7.57 0.02 9.93
st <- proc.time()
a13 <- vector('numeric', N)
a23 <- vector('list', N)
a33 <- vector('numeric', N)
for (i in 1:N){
a13[i] <- i
a23[[i]] <- cumsum(1:i)
a33[i] <- sum(1:i)
}
proc.time() - st
## user system elapsed
## 7.76 0.00 8.20
這個結果顯示sapply最快，有preallocate memory的for-loop差不多
而沒有preallocate memory的for-loop最慢
但是這裡還有一件事要注意
就是sapply跟有preallocate memory的for-loop並非總是最快
有時候反而會比沒有preallocate memory的for-loop最慢
而且在記憶體相對少時
沒有preallocate memory的for-loop跑得出來結果
而sapply跟有preallocate memory的for-loop會跑不出來，因為記憶體不足
因此，在這方面需要去衡量你的運算是否需要消耗大量記憶體
如果是，那麼preallocate memory對你有弊無利
這方面需要經驗去判斷，但是我還是建議初學者多多使用preallocate memory
但是這裡有一個有趣的結果(完全超乎預期的結果)：
我把上面的程式碼做一點改變(下面我用紅色標註我做改變的地方)
N = 5e4
st <- proc.time()
a11 <- c()
a21 <- list()
a31 <- c()
for (i in 1:N){
a11[i] <- i
a21[[i]] <- rnorm(round(mean(a11)/10))
a31[i] <- sum(a11)
}
proc.time() - st
## user system elapsed
## 12.87 0.11 12.98
st <- proc.time()
a12 <- sapply(1:N, function(i)i)
a22 <- lapply(1:N, function(i) rnorm(round(mean(a12[1:i])/10)))
a32 <- sapply(1:N, function(i) sum(a12[1:i]))
proc.time() - st
user system elapsed
17.41 0.08 17.49
st <- proc.time()
a13 <- vector('numeric', N)
a23 <- vector('list', N)
a33 <- vector('numeric', N)
for (i in 1:N){
a13[i] <- i
a23[[i]] <- rnorm(round(mean(a13[1:i])/10))
a33[i] <- sum(a13[1:i])
}
proc.time() - st
user system elapsed
18.75 0.16 18.90
如果你透過了外來變數來計算你其他的值
而且你的外生變數不斷的變化大小下
先生成好外生變數，再進行取子集的動作反而會更慢
這個結果，讓我滿意外的，我還沒有想過這個要怎麼解釋
可能看有沒有人可以幫忙回答這個問題
註二：
我有遇過這種情況，不過目前還不清楚出現的條件為何，
我的猜測是運算的複雜程度，我給一個我手邊有的測試：
(我只跑了三四次，都是lapply比較慢，有空的人可以跑跑看rbenchmark)
N = 1e4
st <- proc.time()
a12 <- lapply(1:N, function(i) replicate(10, rnorm(1000)))
b <- rnorm(10)
a22 <- lapply(1:N, function(i) a12[[i]] %*% b + rnorm(1000))
a32 <- lapply(1:N, function(i) lm(a22[[i]] ~ a12[[i]]))
a42 <- lapply(1:N, function(i) fitted(a32[[i]]))
a52 <- lapply(1:N, function(i) resid(a32[[i]]))
proc.time() - st
## user system elapsed
## 28.63 0.31 28.94
st <- proc.time()
a13 <- vector('list', N)
a23 <- vector('list', N)
a33 <- vector('list', N)
a43 <- vector('list', N)
a53 <- vector('list', N)
b <- rnorm(10)
for (i in 1:N){
a13[[i]] <- replicate(10, rnorm(1000))
a23[[i]] <- a12[[i]] %*% b + rnorm(1000)
a33[[i]] <- lm(a22[[i]] ~ a12[[i]])
a43[[i]] <- fitted(a32[[i]])
a53[[i]] <- resid(a32[[i]])
}
proc.time() - st
## user system elapsed
## 28.1 0.2 28.3
[關鍵字]: preallocated memory