其实一直想讨论这个议题，只是迟迟没有去写这个
这次就想说来分享一下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