为什么sapply比样本大小的循环要慢？

Question

所以我们假设我想使用向量X = 2 * 1：N并将e提升到每个元素的指数。 （是的，我认识到最好的方法是简单地通过向量化exp（X），但是这一点要比较for循环和sapply）。那么我通过增量测试不同样本大小的三种方法（一种是for循环，两种是以不同的方式应用sapply）并测量相应的时间来进行测试。然后我绘制每种方法的样本量N与时间t的关系。

每种方法都由“#####”表示。

k <- 20 
t1 <- rep(0,k) 
t2 <- rep(0,k) 
t3 <- rep(0,k) 
L <- round(10^seq(4,7,length=k)) 


for (i in 1:k) { 
    X <- 2*1:L[i] 
    Y1 <- rep(0,L[i]) 
    t <- system.time(for (j in 1:L[i]) Y1[j] <- exp(X[j]))[3] ##### 
    t1[i] <- t 
} 

for (i in 1:k) { 
    X <- 2*1:L[i] 
    t <- system.time(Y2 <- sapply(1:L[i], function(q) exp(X[q])))[3] ##### 
    t2[i] <- t 
} 

for (i in 1:k) { 
    X <- 2*1:L[i] 
    t <- system.time(Y3 <- sapply(X, function(x) exp(x)))[3] ##### 
    t3[i] <- t 
} 

plot(L, t3, type='l', col='green') 
lines(L, t2,col='red') 
lines(L, t1,col='blue') 

plot(log(L), log(t1), type='l', col='blue') 
lines(log(L), log(t2),col='red') 
lines(log(L), log(t3), col='green') 

我们得到以下结果。 剧情的N随T：

剧情日志（N）与日志（吨）

蓝色情节是for循环方法，以及红色和绿色曲线是sapply方法。在常规情节中，您可以看到，随着样本量变大，for循环方法比sapply方法更受欢迎，这不是我所期望的。如果你看一下log-log图（为了更容易区分较小的N结果），我们可以看到sapply的预期结果比用于小N的循环更有效。

有谁知道为什么sapply缩放更慢比循环与样本大小？谢谢。

Answer 1

你没有考虑为结果向量分配空间所需的时间Y1。随着样本规模的增加，分配Y1所花费的时间将成为执行时间的一个较大份额，并且执行替换所花费的时间将变少。

sapply总是为结果分配内存，所以这就是随着样本大小增加而效率降低的原因之一。 gagolews也有一个非常好的关于sapply呼叫simplify2array。那（可能）增加了另一个副本。

---

一些更多的测试后，它看起来像lapply依然看好比含有for循环一个字节编译功能相同或更慢，视物变大。我不知道如何在do_lapply解释这一点，除了可能是这一行：

if (MAYBE_REFERENCED(tmp)) tmp = lazy_duplicate(tmp); 

或者可能具有的东西怎么lapply构造函数调用......但我主要是投机。

这是我用来测试的代码：

k <- 20 
t1 <- rep(0,k) 
t2 <- rep(0,k) 
t3 <- rep(0,k) 
L <- round(10^seq(4,7,length=k)) 
L <- round(10^seq(4,6,length=k)) 

# put the loop in a function 
fun <- function(X, L) { 
    Y1 <- rep(0,L) 
    for (j in 1:L) 
    Y1[j] <- exp(X[j]) 
    Y1 
} 
# for loops often benefit from compiling 
library(compiler) 
cfun <- cmpfun(fun) 

for (i in 1:k) { 
    X <- 2*1:L[i] 
    t1[i] <- system.time(Y1 <- fun(X, L[i]))[3] 
} 
for (i in 1:k) { 
    X <- 2*1:L[i] 
    t2[i] <- system.time(Y2 <- cfun(X, L[i]))[3] 
} 
for (i in 1:k) { 
    X <- 2*1:L[i] 
    t3[i] <- system.time(Y3 <- lapply(X, exp))[3] 
} 
identical(Y1, Y2)   # TRUE 
identical(Y1, unlist(Y3)) # TRUE 
plot(L, t1, type='l', col='blue', log="xy", ylim=range(t1,t2,t3)) 
lines(L, t2, col='red') 
lines(L, t3, col='green') 

Answer 2

尝试取出多余的功能（x）的代码运行每次迭代。它必须有很多开销。我没有将二者分开，但for循环也应该包括一个苹果，苹果的比较像这样所有相关工作：

t <- system.time(Y1 <- rep(0,L[i])) + system.time(for (j in 1:L[i]) Y1[j] <- exp(X[j]))[3] ##### 

更快sapply：

for (i in 1:k) { 
    X <- 2*1:L[i] 
    t <- system.time(Y4 <- sapply(X,exp)[3]) ##### 
    t4[i] <- t 
} 

它仍然较慢，但比前两个sapply更接近。

Answer 3

大部分点之前已经提出，但...

1. sapply()使用lapply()然后格式化支付使用simplify2array()结果的一次性成本。

2. lapply()创建一个长的向量，然后创建大量的短（长度为1）的向量，而for循环生成一个单独的长向量。

3. 写入的sapply()与for循环相比具有额外的函数调用。

4. 使用gcinfo(TRUE)可以让我们看到垃圾回收器的运行情况，并且每种方法都会导致垃圾回收器多次运行 - 这可能相当昂贵，而且不是完全确定性的。

点1 - 3需要在实施例的人工上下文被解释 - exp()是一种快速作用，夸大存储器分配（2）中，函数评估（3），和一维的相对贡献时间成本（1）。第4点强调需要以系统的方式重复计时。

我开始加载编译器和microbenchmark软件包。我专注于最大尺寸仅为

library(compiler) 
library(microbenchmark) 
n <- 10^7 

在我的第一个实验中我用简单的分配替换exp()，并试图代表结果的不同方式的for循环 - 数值的载体，或者数字载体的名单如lapply()所示。

fun0n <- function(n) { 
    Y1 <- numeric(n) 
    for (j in seq_len(n)) Y1[j] <- 1 
} 
fun0nc <- compiler::cmpfun(fun0n) 

fun0l <- function(n) { 
    Y1 <- vector("list", n) 
    for (j in seq_len(n)) Y1[[j]] <- 1 
} 
fun0lc <- compiler::cmpfun(fun0l) 

microbenchmark(fun0n(n), fun0nc(n), fun0lc(n), times=5) 
## Unit: seconds 
##  expr  min  lq  mean median  uq  max neval 
## fun0n(n) 5.620521 6.350068 6.487850 6.366029 6.933915 7.168717  5 
## fun0nc(n) 1.852048 1.974962 2.028174 1.984000 2.035380 2.294481  5 
## fun0lc(n) 1.644120 2.706605 2.743017 2.998258 3.178751 3.187349  5 

因此，编译for循环会付出代价，并且生成向量列表的成本相当高。这个内存成本再次被for循环体的简单性所放大。

我的下一个实验探讨不同*apply()

fun2s <- function(n) 
    sapply(raw(n), function(i) 1) 
fun2l <- function(n) 
    lapply(raw(n), function(i) 1) 
fun2v <- function(n) 
    vapply(raw(n), function(i) 1, numeric(1)) 

microbenchmark(fun2s(n), fun2l(n), fun2v(n), times=5) 
## Unit: seconds 
##  expr  min  lq  mean median  uq  max neval 
## fun2s(n) 4.847188 4.946076 5.625657 5.863453 6.130287 6.341282  5 
## fun2l(n) 1.718875 1.912467 2.024325 2.141173 2.142004 2.207105  5 
## fun2v(n) 1.722470 1.829779 1.847945 1.836187 1.845979 2.005312  5 

有一个大的成本在sapply()简化步骤; vapply()比lapply()（我保证返回的类型）没有任何性能损失更强大，所以它应该是我在这个家族中的首选功能。

最后，我比较了迭代到vapply()，其中结果是一个向量列表。

fun1 <- function(n) { 
    Y1 <- vector("list", n) 
    for (j in seq_len(n)) Y1[[j]] <- exp(0) 
} 
fun1c <- compiler::cmpfun(fun1) 

fun3 <- function(n) 
    vapply(numeric(n), exp, numeric(1)) 
fun3fun <- function(n) 
    vapply(numeric(n), function(i) exp(i), numeric(1)) 

microbenchmark(fun1c(n), fun3(n), fun3fun(n), times=5) 
## Unit: seconds 
##  expr  min  lq  mean median  uq  max neval 
## fun1c(n) 2.265282 2.391373 2.610186 2.438147 2.450145 3.505986  5 
##  fun3(n) 2.303728 2.324519 2.646558 2.380424 2.384169 3.839950  5 
## fun3fun(n) 4.782477 4.832025 5.165543 4.893481 4.973234 6.346498  5 

microbenchmark(fun1c(10^3), fun1c(10^4), fun1c(10^5), 
       fun3(10^3), fun3(10^4), fun3(10^5), 
       times=50) 
## Unit: microseconds 
##   expr min lq mean median uq max neval 
## fun1c(10^3) 199 215 230 228 241 279 50 
## fun1c(10^4) 1956 2016 2226 2296 2342 2693 50 
## fun1c(10^5) 19565 20262 21671 20938 23410 24116 50 
## fun3(10^3) 227 244 254 254 264 295 50 
## fun3(10^4) 2165 2256 2359 2348 2444 2695 50 
## fun3(10^5) 22069 22796 23503 23251 24393 25735 50 

编译为for循环和vapply()是颈部相连;额外的函数调用几乎使vapply()的执行时间加倍（再一次，这个效果由于示例的简单性而被夸大了）。在一系列尺寸范围内，相对速度似乎没有太大的变化