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.031775 0.032144 0.03238918 0.032267 0.032554 0.037884
## fibo_loop(10) 0.005576 0.005740 0.00615082 0.005822 0.005986 0.030463
## 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) 509.120698 515.519855 521.34994184 516.9512675 518.4165050
## fibo_loop(30) 0.011849 0.014309 0.03540186 0.0201925 0.0565185
## max neval cld
## 585.327890 100 a
## 0.068716 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.031857 0.032431 0.03283731 0.032800 0.033169 0.035260
## fibo_loop(10) 0.005617 0.005863 0.00627710 0.006068 0.006232 0.024149
## fibo_memoise(10) 0.002091 0.002173 0.00308484 0.002296 0.002419 0.080442
## 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) 510.783453 516.0568115 521.88163189 517.4019395 518.6915125
## fibo_loop(30) 0.011972 0.0142270 0.03133015 0.0170355 0.0523160
## fibo_memoise(30) 0.002460 0.0031775 0.01727945 0.0200080 0.0284335
## max neval cld
## 584.970698 100 a
## 0.063099 100 b
## 0.178637 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.