Otimizando o Tempo do Cálculo da Sequência de Fibonacci no R

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.030463 0.0310370 0.03140067 0.031324 0.0316110 0.035219
##       fibo_loop(10) 0.005494 0.0056785 0.00616517 0.005822 0.0060475 0.033333
##  neval cld
##    100   b
##    100  a
microbenchmark(fibo_recursiva(30),
               fibo_loop(30),
               unit = "ms")
## Unit: milliseconds
##                expr        min          lq         mean      median          uq
##  fibo_recursiva(30) 495.053721 499.7019320 505.95837128 501.0655305 504.0566035
##       fibo_loop(30)   0.011562   0.0130175   0.03198902   0.0189215   0.0526645
##         max neval cld
##  583.157268   100   b
##    0.062812   100  a

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.031652 0.0362030 0.06383987 0.0373305 0.0385810 2.641876
##       fibo_loop(10) 0.005699 0.0063755 0.05585717 0.0076670 0.0087125 4.606719
##    fibo_memoise(10) 0.002091 0.0022960 0.00335175 0.0025010 0.0027265 0.072775
##  neval cld
##    100   a
##    100   a
##    100   a
microbenchmark(fibo_recursiva(30),
               fibo_loop(30),
               fibo_memoise(30),
               unit = "ms")
## Unit: milliseconds
##                expr        min          lq         mean      median         uq
##  fibo_recursiva(30) 493.992887 497.7885235 504.49642895 499.8109510 502.543601
##       fibo_loop(30)   0.011234   0.0135505   0.03340270   0.0178350   0.054817
##    fibo_memoise(30)   0.002460   0.0032800   0.01625855   0.0085895   0.027347
##         max neval cld
##  584.716621   100   b
##    0.073595   100  a 
##    0.176423   100  a

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.