Hoje mesmo pensei em comparar o tempo de excução de uma função com o mesmo objetivo, mas escrita de duas formas diferentes. Queria ver se uma recursão ou um loop são mais rápidos de serem executados no R. Para isso, escrevi duas versões de uma função para calcular o n-ésimo termo da sequência de Fibonacci. Minha hipótese é que a recursão seria mais lenta do que um loop, mas eu gostaria de quantificar isso. Portanto, criei as funções fibo_recursiva e fibo_loop para testar a minha hipótese.
fibo_recursiva <- function(n){
if (n <= 2){
return(1)
} else {
return(fibo_recursiva(n-1) + fibo_recursiva(n-2))
}
}
fibo_loop <- function(n){
if (n <= 2){
return(1)
} else {
x <- c(1,1)
for (j in 3:n){
x[j] <- x[j-1] + x[j-2]
}
return(tail(x, 1))
}
}
Perceba que ambas informam o mesmo resultado numérico para os primeiros termos da sequência de Fibonacci:
fibo_recursiva(10)
## [1] 55
fibo_loop(10)
## [1] 55
fibo_recursiva(30)
## [1] 832040
fibo_loop(30)
## [1] 832040
Ao compará-las para estimar os tempos de processamento para os mesmo termos 10 e 30 da sequência, que que surge a minha surpresa
library(microbenchmark)
microbenchmark(fibo_recursiva(10),
fibo_loop(10),
unit = "ms")
## Unit: milliseconds
## expr min lq mean median uq max
## fibo_recursiva(10) 0.031898 0.032226 0.03251382 0.032472 0.032718 0.033989
## fibo_loop(10) 0.005617 0.005781 0.00608809 0.005904 0.006027 0.022181
## neval cld
## 100 a
## 100 b
microbenchmark(fibo_recursiva(30),
fibo_loop(30),
unit = "ms")
## Unit: milliseconds
## expr min lq mean median uq
## fibo_recursiva(30) 508.855961 517.8171055 523.04059980 518.989029 520.6031375
## fibo_loop(30) 0.011767 0.0129765 0.02967949 0.016236 0.0472935
## max neval cld
## 584.651513 100 a
## 0.070028 100 b
Para o cálculo do décimo elemento, a recursão levou, em média 0.03140067ms para calcular o décimo elemento da sequência, enquando o loop precisou de apenas 0.00616517ms, em média. Ou seja, é uma diferença de uma ordem de magnitude. Mas, ao calcular o trigésimo termo, a diferença aumenta muito. Foram 4 ordens de magnitude a mais (505.95837128ms versus 0.03198902ms).
Isso se deve à forma como uma função recursiva é executada. Para calcular o décimo termo, temos o seguinte:
F(10) = F(9) + F(8)
F(10) = F(8) + F(7) + F(7) + F(6)
F(10) = F(7) + F(6) + F(6) + F(5) + F(6) + F(5) + F(5) + F(4)
F(10) = ...
E isso vai pesando nos cálculos. Assim, a árvore de recursão vai crescendo muito, e calculando muitos termos que são desnecessários. Note como na terceira linha F(6) e F(5) são calculadas, cada uma, três vezes.
O livro R Inferno tem uma solução para isso chamada memoization. Ela consiste em salvar em cache resultados intermediários de uma função. Assim, quando o mesmo valor da função deveria ser recalculado, o resultado já está disponível e se economiza poder de processamento e, consequentemente, tempo.
O exemplo de memoização que o livro fornece é justamente utilizando a sequência de Fibonacci:
fibo_memoise <- local({
memory <- list()
function(n) {
valueName <- as.character(n)
if (!is.null(memory[[valueName]])) return(memory[[valueName]])
if (n == 0) return(0)
if (n == 1) return(1)
res <- Recall(n - 1) + Recall(n - 2)
memory[[valueName]] <<- res # store results
res
}
})
Rodando novamente nosso benchmark, o resultado obtido é muito bom:
microbenchmark(fibo_recursiva(10),
fibo_loop(10),
fibo_memoise(10),
unit = "ms")
## Unit: milliseconds
## expr min lq mean median uq max
## fibo_recursiva(10) 0.031898 0.0323900 0.03283116 0.032718 0.0331485 0.035055
## fibo_loop(10) 0.005617 0.0058425 0.00625701 0.006027 0.0062730 0.023329
## fibo_memoise(10) 0.002091 0.0021320 0.00312215 0.002296 0.0024190 0.083189
## neval cld
## 100 a
## 100 b
## 100 c
microbenchmark(fibo_recursiva(30),
fibo_loop(30),
fibo_memoise(30),
unit = "ms")
## Unit: milliseconds
## expr min lq mean median uq
## fibo_recursiva(30) 509.524917 516.5006570 522.75938326 518.6592045 520.0424625
## fibo_loop(30) 0.011767 0.0140425 0.03374669 0.0357520 0.0525620
## fibo_memoise(30) 0.002419 0.0030545 0.01452835 0.0132225 0.0221605
## max neval cld
## 580.541878 100 a
## 0.075030 100 b
## 0.161417 100 b
Dessa vez, a função fibo_memoise foi mais rápida do que o loop, levando metade do tempo, em média. Ou seja, é um ganho impressionante de desempenho para a função recursiva.