为什么 R diff 功能慢？

Question

在 R 中处理向量时，diff 函数计算每个值与前一个值之间的差异。来自 ?diff:

If x is a vector of length n and differences = 1, then the computed result is equal to the successive differences x[(1+lag):n] - x[1:(n-lag)]

但是，当我测试 diff 函数的执行时间与它们的理论表达式（使用 microbenchmark 包中的 microbenchmark 函数）时，diff 函数比较慢.这是我的代码：

library(microbenchmark)

mb.diff1 <- function(n, seed){
  set.seed(seed)
  vec <- runif(n)
  out <- diff(vec)
  return(out)
}

mb.diff2 <- function(n, seed){
  set.seed(seed)
  vec <- runif(n)
  out <- vec[2:n]-vec[1:(n-1)]
  return(out)
}

times.diff1 <- c()  
times.diff2 <- c()
vec.sizes <- c(1e1, 1e2, 1e3, 1e4)
for (n in vec.sizes){
  bench <- microbenchmark(
    mb.diff1(n,1),
    mb.diff2(n,1))
  times.median <- aggregate(
    bench$time,
    by  = list(bench$expr), 
    FUN = median)
  times.diff1 <- c(times.diff1, times.median[1,2])
  times.diff2 <- c(times.diff2, times.median[2,2])
}

perf.ratio <- times.diff1/times.diff2
names(perf.ratio) <- vec.sizes
print(perf.ratio)

我完成了1e4的vec.sizes，所以你们的执行时间不会太长，但我让他们执行到1e7。你可以在这里看到结果：

如您所见，diff 函数对于所有向量大小都较慢。商趋于减小，因为在这两种情况下执行时间似乎都是矢量大小的线性函数，所以我们不能说 diff 随着 n 的增加表现得更好。那么问题来了：

（显而易见的问题）我在测量执行时间时是否在我的代码中做错了什么？
diff 函数比理论表达式慢的原因是什么？
你知道比 x[(1+lag):n] - x[1:(n-lag)] 更有效的计算差异向量的方法吗？

我在 Linux 中使用 R 3.1.2。

非常感谢您。

Answer 1

这里有一些代码可以帮助扩展和说明我在评论中提出的观点。

library(microbenchmark)

mb.diff2 <- compiler::cmpfun(function(vec) {
  n <- length(vec)
  vec[2:n]-vec[1:(n-1L)]
})

times.diff1 <- c()  
times.diff2 <- c()
times.diff3 <- c()
vec.sizes <- c(1e1, 1e2, 1e3, 1e4, 1e5)

for (n in vec.sizes) {
  set.seed(21)
  vec <- runif(n)
  bench <- microbenchmark(diff(vec), mb.diff2(vec), diff.default(vec))
  times.median <- aggregate(bench$time, by = list(bench$expr), FUN = median)
  times.diff1 <- c(times.diff1, times.median[1,2])
  times.diff2 <- c(times.diff2, times.median[2,2])
  times.diff3 <- c(times.diff3, times.median[3,2])
}

setNames(times.diff1/times.diff2, vec.sizes)
setNames(times.diff1/times.diff3, vec.sizes)

首先，您会注意到我编译了 mb.diff2 函数。这是因为 diff 和 diff.default 是 byte-compiled。我也把 n 的计算放在 mb.diff2 里面，因为计算向量长度应该是测量函数调用的一部分。

这是计时结果，以及我的 sessionInfo():

R> setNames(times.diff1/times.diff2, vec.sizes)
       10       100      1000     10000     1e+05 
3.5781536 2.3330988 1.2488135 0.9011312 0.9660411 
R> setNames(times.diff1/times.diff3, vec.sizes)
       10       100      1000     10000     1e+05 
1.5945010 1.4609283 1.1021190 1.0034623 0.9987618 
R> sessionInfo()
R version 3.3.2 (2016-10-31)
Platform: x86_64-pc-linux-gnu (64-bit)
Running under: Ubuntu 16.04.1 LTS

locale:
 [1] LC_CTYPE=en_US.UTF-8       LC_NUMERIC=C              
 [3] LC_TIME=en_US.UTF-8        LC_COLLATE=en_US.UTF-8    
 [5] LC_MONETARY=en_US.UTF-8    LC_MESSAGES=en_US.UTF-8   
 [7] LC_PAPER=en_US.UTF-8       LC_NAME=C                 
 [9] LC_ADDRESS=C               LC_TELEPHONE=C            
[11] LC_MEASUREMENT=en_US.UTF-8 LC_IDENTIFICATION=C       

attached base packages:
[1] stats     graphics  grDevices utils     datasets  methods   base     

other attached packages:
[1] microbenchmark_1.4-2

loaded via a namespace (and not attached):
 [1] Rcpp_0.12.9      digest_0.6.8     MASS_7.3-45      grid_3.3.2      
 [5] plyr_1.8.4       gtable_0.1.2     magrittr_1.5     scales_0.3.0    
 [9] ggplot2_1.0.1    stringi_0.4-1    reshape2_1.4.1   proto_0.3-10    
[13] tools_3.3.2      stringr_1.0.0    munsell_0.4.2    compiler_3.3.2  
[17] colorspace_1.2-6

为什么 R diff 功能慢？

Why is R diff function slow?

diff

benchmarking

r