Perché la scala è più lenta di quella del ciclo con la dimensione del campione?

Question

Quindi diciamo che voglio prendere il vettore X = 2 * 1: N e aumentare e all'esponente di ogni elemento. (Sì, riconosco che il modo migliore per farlo è semplicemente con vectorization exp (X), ma il punto di questo è confrontare per loop con sapply). Bene, ho provato testando in modo incrementale tre metodi (uno con loop for, due con sapply applicato in un modo diverso) con diverse dimensioni del campione e misurando il tempo corrispondente. Quindi tracciamo la dimensione del campione N rispetto al tempo t per ciascun metodo.

Ogni metodo è indicato da "#####".

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') 

Otteniamo i seguenti risultati. Terreno di N vs t:

Aree log (N) vs log (t)

La trama blu è il ciclo for metodo, e le trame rosse e verdi sono i metodi sapply. Nel plot regolare, è possibile notare che, man mano che la dimensione del campione aumenta, il metodo for loop viene fortemente favorito rispetto ai metodi sapply, il che non è affatto quello che mi sarei aspettato. Se guardi la trama del log-log (per distinguere più facilmente i risultati N più piccoli) vediamo il risultato atteso che Sapply è più efficiente di loop per small N.

Qualcuno sa perché sapply scala più lentamente che per loop con dimensioni del campione? Grazie.

Answer 1

Non si tiene conto del tempo necessario per allocare lo spazio per il vettore risultante Y1. All'aumentare della dimensione del campione, il tempo necessario per allocare Y1 diventa una quota maggiore del tempo di esecuzione e il tempo necessario per eseguire la sostituzione diventa una condivisione più piccola.

sapply assegna sempre la memoria per il risultato, quindi questa è una ragione per cui sarebbe meno efficiente all'aumentare della dimensione del campione. gagolews ha anche un ottimo punto su sapply chiamando il simplify2array. Questo (probabile) aggiunge un'altra copia.

---

Dopo altri test, sembra che lapply è ancora circa lo stesso o più lento di una funzione di byte-compilato contenente un ciclo, come gli oggetti diventano più grandi. Non sono sicuro di come spiegare questo, altro che forse questa linea in do_lapply:

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

O forse qualcosa di come lapply costruisce la chiamata di funzione ... ma sto per lo più speculare.

Ecco il codice che ho usato per prova:

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

provate a prendere la funzione in eccesso (x) il codice che viene eseguito ogni iterazione. Deve avere un sacco di spese generali. Io non separare le due cose, ma il ciclo dovrebbe includere anche tutto il lavoro associato per le mele alle mele confronto come questo:

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

A molto più veloce sapply:

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

E 'ancora più lento, ma molto più vicino dei primi due di soldi.

Answer 3

La maggior parte dei punti sono stati fatti prima, ma ...

1. sapply() utilizza lapply() e poi paga un costo una tantum di formattare il risultato utilizzando simplify2array().

2. lapply() crea un vettore lungo e quindi un numero elevato di vettori corti (lunghezza 1), mentre il ciclo for genera un singolo vettore lungo.

3. Il sapply() come scritto ha una chiamata di funzione aggiuntiva rispetto al ciclo for.

4. L'utilizzo di gcinfo(TRUE) consente di visualizzare il garbage collector in azione e ogni approccio determina l'esecuzione del garbage collector più volte, che può essere piuttosto costoso e non completamente deterministico.

Points 1 - 3 debbano essere interpretate nel contesto artificiale dell'esempio - exp() è una funzione veloce, esagerare il contributo relativo di allocazione di memoria (2), la valutazione della funzione (3), e mono i costi di tempo (1). Il punto 4 sottolinea la necessità di replicare i tempi in modo sistematico.

Ho iniziato caricando i pacchetti del compilatore e del microbenchmark. Mi sono concentrato sulla più grande per dimensioni solo

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

Nel mio primo esperimento ho sostituito exp() con semplice assegnazione, ed ho provato diversi modi di rappresentare il risultato nel ciclo for - un vettore di valori numerici, o un elenco di vettori numerici come implicito da lapply().

Quindi paga per compilare il ciclo for, e c'è un costo abbastanza consistente per generare un elenco di vettori. Ancora una volta questo costo di memoria è amplificato dalla semplicità del corpo del ciclo for.

mio prossimo esperimento ha esplorato diversi *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 

C'è un grande costo per il passaggio semplificazione sapply(); vapply() è più robusto di lapply() (sono garantito il tipo di reso) senza penalità di prestazioni, quindi dovrebbe essere la mia funzione di go-in in questa famiglia.

Infine, ho confrontato l'iterazione in vapply() in cui il risultato è un elenco di vettori.

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 

Il elaborate per ciclo e vapply() sono collo-in-collo; la chiamata di funzione extra quasi raddoppia il tempo di esecuzione di vapply() (ancora, questo effetto è esagerato dalla semplicità dell'esempio). Non sembra esserci molto cambiamento nella velocità relativa in una gamma di dimensioni