Почему R diff работает медленно?

Question

При работе с векторами в R функция diff вычисляет различия между каждым значением и предыдущим. Из ?diff:

Если x вектор длины n и differences = 1, то вычисленный результат равен последовательных разностей 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) 

я закончил с vec.sizes из 1E4, так что время excution для вас, ребята, не слишком долго, но я заставляю их идти до 1e7. Вы можете увидеть здесь результаты:

Как вы можете видеть, функция diff является медленнее всех векторных размеров. Фактор имеет тенденцию уменьшаться, поскольку в обоих случаях время исполнения является линейной функцией от векторного размера, поэтому мы не можем сказать, что diff лучше работает с ростом n. Таким образом, возникают вопросы:

1. (Очевидный вопрос) Я делаю что-то неправильно в своем коде при измерении времени выполнения?
2. Что может быть причиной того, что функция diff работает медленнее, чем их теоретическое выражение?
3. Знаете ли вы самый эффективный способ вычисления вектора различий, чем x[(1+lag):n] - x[1:(n-lag)]?

Я использую R 3.1.2 в Linux.

спасибо, что заранее.

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 байт-скомпилированы. Я также поместил вычисление 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