Caché de funciones en R

En algunas ocasiones puede ser que en la implementación de un algoritmo se llame continuamente a la misma función utilizando los mismos parámetros. Algo que se puede de forma habitual en problemas recesivos. En caso de que la función se ejecute rápidamente no será un problema mayor, pero en las ocasiones que no es así aparecen problemas de rendimiento. Para solucionar estos problemas se pueden almacenar los resultados en una tabla y, antes de ejecutar la función, comprobar si la tarea se ha realizado previamente. En R esto se puede realizar automáticamente con el paquete memoise. En el que se encuentra la función memoise con la que se puede generar copias que cachea cualquier función.

Función de ejemplo

Supongamos que tenemos una función que tarda un segundo en obtener un resultado:

slow <- function(x) {
  Sys.sleep(1)
  x + 1
}

En caso se que se ejecute esta función 10 veces el tiempo en finalizar será próximo a unos 10 segundos. Esto se puede comprobar simplemente utilizando el siguiente código:

system.time(for (i in 1:10) print(slow(i)))

Ahora, utilizando el paquete memoise se puede crear una versión cachead de la función:

library(memoise)

slow.cache <- memoise(slow)

Igual que antes el tiempo de ejecución de la función será de unos 10, pero la segunda vez que se ejecute el código será prácticamente instantáneo. Esto se puede comprobar ejecutando dos veces la siguiente línea.

system.time(for (i in 1:10) print(slow.cache(i)))

En el caso de que sea necesario borrar los resultados ya almacenados de una función cachada simplemente se ha de utilizar la función forget del mismo paquete:

forget(slow.cache)

Este paquete permite mejorar el rendimiento de algunos de nuestros algoritmos de una forma fácil sin la necesidad de modificar mucho código.

Ejemplo en un problema real

El ejemplo anterior muestra la potencia de la función memoise, pero no es habitual encontrase con problemas como este. Las situaciones en la que este paquete se hace realmente útil es en los problemas recursivos como puede ser la obtención de Sucesión de Fibonacci. Los números de Fibonacci quedan definidos por la ecuación:

f(n) <- f(n-1) + f(n-2)

partiendo de dos primeros valores predeterminados:

f(1) = 1
f(2) = 2

La implementación de esta función en R se puede realizar con

fibonacci <- function(n) {
  if (n < 2) {
     return(n)
  } else {
    return(fibonacci (n-1) + fibonacci (n-2))
  }
}

Se puede comprobar el tiempo que tarda en obtener los primeros 40 número de la serie:

system.time(f_original <- fibonacci_cache(40))

En mi ordenador ha tardado unos 120,237 segundos. Ahora se puede comprobar el tiempo el tiempo que tardaría en la función cacheada:

fibonacci <- memoise(fibonacci)
system.time(f_cache_1 <- fibonacci (40))

La salida de la función memoise se ha asignado a la variable con el mismo nombre que la original. En caso de que esto no se haga así no se obtendrá una mejora de los resultados debido a que internamente se llamará a una función no cachada.

En esta ocasión R solamente ha tardado unos 0,019 segundos. Los que supone solamente un del 0,016% del tiempo original.

En caso de que se repita el ejercicio, en este caso el tiempo ser cero.

system.time(f_cache_2 <- fibonacci (40))

Obviamente los resultados en las tres ocasiones son el mismo: 102334155.