3.6 Iteración y Recursión

¿Los ciclos son lentos en R? Sí y no. Todo depende de como se utilice.

Para comprender lo anterior, primero hay que entender como R almacena sus objetos. Para tener un entendimiento completo sobre todas las estructuras, es recomendable leer el capitulo 2 de Advance R; por el momento sólo se dará una introducción sobre como se comportan los vectores y las listas.

Como ya se habia mencionado, cuando se hace algún objeto en R, como un vector o una lista, a estos se les asigna un nombre para poder identificarlos posteriormente. Véase los siguientes resultados.

x <- 1:5
tracemem(x)
[1] "<0x7fda847a4ec8>"

El resultado anterior es un identificador de la dirección en formato hexadecimal del vector x en memoria.

y <- x
tracemem(y)
[1] "<0x7fda847a4ec8>"

Ahora el nombre “y” esta asociado con la variable x, aunque en realidad los nombres “y” y “x” apuntan hacia un mismo objeto y eso puede verse con los anteriores resultados.

¿Qué sucederá cuando se modifique algún valor en la variable y? ¿Se modificará en esa posición x?

trace_vec <- capture.output(y[[3]] <- 10)
cat(paste(c(strsplit(trace_vec[1],":")[[1]][1],  strsplit(trace_vec[2],":")[[1]][1]), collapse = "\n"))
tracemem[0x7fda847a4ec8 -> 0x7fda86eee4f8]
tracemem[0x7fda86eee4f8 -> 0x7fda8ac62ed8]
cat(paste(c(x[[3]], y[[3]]), collapse = "\n"))
3
10

Los valores del vector x no se modificaron, solo los de y y las anteriores salidas al modificar el tercer elemento en el vector y son por lo que en R se conoce como Copy-on-modify donde básicamente los vectores no son copiados hasta que estos sean modificados. La primera salida es debido a que se realizo una copia de todos los elementos de x y posteriormente se modifico en y el tercer elemento. Véase que x no fue alterado en la ubicación o el identificador en memoria de este.

tracemem(x)
[1] "<0x7fda847a4ec8>"
tracemem(y)
[1] "<0x7fda8ac62ed8>"
  • ¿Si se hubiera modificado algún elemento de x en lugar de y, qué hubiera sucedido?

Ahora, véase el caso con las listas

list_mem <- list(uno = 1:5, dos = 1:7)
list_mem_copy <- list_mem
tracemem(list_mem)
[1] "<0x7fda8a334948>"
tracemem(list_mem_copy)
[1] "<0x7fda8a334948>"

Las listas creadas anteriormente tienen la misma dirección y no sólo eso, si no que cada uno de los elementos de la lista también son los mismos

cat(paste(c(tracemem(list_mem[[1]]),
tracemem(list_mem_copy[[1]]),
tracemem(list_mem[[2]]),
tracemem(list_mem_copy[[2]])), collapse = "\n"))
<0x7fda84c96b10>
<0x7fda84c96b10>
<0x7fda84c96bf0>
<0x7fda84c96bf0>

¿Qué sucedera cuando se modifique algún elemento en list_mem? ¿Sucederá lo mismo que en los vectores?

trace_list <- capture.output(list_mem[[2]] <- 2:8)
cat(strsplit(trace_list[1],":")[[1]][1])
tracemem[0x7fda8a334948 -> 0x7fda891a2e48]

Solo se hizo un cambio en dirección de memoria, ya que en el caso de las listas no se copia todos los elementos, solo se cambia el puntero hacia otro objeto. Véase que en los elementos que no se realizo algúna modificación se sigue apuntando hacia el mismo objeto.

cat(paste(c(tracemem(list_mem[[1]]),
tracemem(list_mem_copy[[1]]),
tracemem(list_mem[[2]]),
tracemem(list_mem_copy[[2]])), collapse = "\n"))
<0x7fda84c96b10>
<0x7fda84c96b10>
<0x7fda82071f90>
<0x7fda84c96bf0>
  • ¿Las direcciones de las listas list_mem y list_mem_copy ahora son diferentes?

En resumen, al modificar algún elemento dentro de un vector, se creó una copia de todos los valores teniendo así dos vectores con diferentes nombres y, cuando se modifica algún elemento en las listas, solo se cambia de dirección el punto correspondiente a ese objeto y los demás enlaces permanecen.

Cuando se hace algún ciclo donde se este agregando o modificando algún vector, internamente se realizarán copias de todo el vector aunque sólo un elemento sea alterado; en ese caso los ciclos iterativos son lentos, pero cuando se utiliza una lista en lugar de un vector el rendimiento mejora bastante. Hay que recordar que R no fue diseñado para ser rápido, aunque usando listas el rendimiento obtenido será mejor al usar un ciclo.

data <- data.frame(matrix(1:100000, ncol = 100))
plus2_byVector <- function(x){
  #Al usar m[[n]] cuando m es un data.frame, véase que se estan tomando vectores
  for(item in 1:length(x)){
    x[[item]] <- x[[item]]+2
  }
  x
}
kable(bench::mark(plus2_byVector(data))[c("min", "median", "mem_alloc", "total_time")], format = "markdown")
min median mem_alloc total_time
1.39ms 1.58ms 1.11MB 429ms 
plus2_byList <- function(x){
  #Al convertir un data.frame en una lista, se agrega un elemento por columna
  x <- as.list(x)
  for(item in 1:length(x)){
    x[[item]] <- x[[item]]+2
  }
  x
}
kable(bench::mark(plus2_byList(data))[c("min", "median", "mem_alloc", "total_time")], format = "markdown")
min median mem_alloc total_time
150µs 188µs 813KB 257ms

Otro punto que hay que considerar es que no siempre existirá una manera sencilla de usar algún funcional para remplazar a un ciclo, ya sea al modificar en algún lugar un objeto o al usar recursión, ya que en este último caso se depende de índices o de elementos anteriores que con un funcional no sería sencillo de resolver.

En general, hay ocasiones en las que un ciclo debe permanecer explícitamente para dar solución a un problema, tal es el caso de un modificación en una estructura en cada iteración; esto se puede remplazar con algún funcional aunque el código puede perder legibilidad. Otra circunstancia donde los ciclos no deben ser remplazados por un funcional son las relaciones recursivas ya que estas dependen de las posiciones dentro de una estructura, lo cual si puede ser difícil de plasmar en un funcional. Finalmente, cuando se tenga una solución implementada con un ciclo while, será complicado remplazar este por funciones como de la familia apply.

En el ámbito de la recursión, se pueden tener varios problemas y uno de los principales son la manera en que estos son tratados dentro de los lenguajes no funcionales, ya que el almacenamiento en este tipo de instrucciones puede ser demasiado. La manera en que trabajan las funciones recursivas es llamando internamente a las mismas funciones hasta llegar a un caso base, y mientras se opere con los resultados de las funciones internas, estos deben ser almacenados en la memoria y la forma en que estos son almacenados es en una pila conocida como Call Stack.

Dependiendo del lenguaje de programación la administración de la pila de llamadas puede cambiar, aunque esta siempre tendrá un límite de almacenamiento. En el caso de la recursión puede ser sencillo llenar esta y obtener una excepción indicando esta situación. Para tales casos, se puede remplazar la implementación de las funciones con diferentes técnicas; una de ellas se llama Memoization en la cual se guarda, en un ambiente fuera de la pila de llamadas, los resultados que se han obtenido de las funciones recursivas. Por ejemplo, si se esta tratando el problema de tener los primeros \(n\) números de fibonacci y previamente se corrió fibonacci(m) donde \(m<n\), al momento de hacer fibonacci(n) está buscará si existen registros de llamadas previas y comenzará desde ese punto, por lo que fibonacci(n) no tendrá que calcular los \(n-1\) nuevamente, si no, solo los faltantes; por lo que, si se tiene el suficiente espacio, el problema del límite de memoria en la Call Stack quedará resuelto. En los siguientes enlaces se dejan algunos ejemplos de esto.

Otra forma de solucionar el problema de la recursión, es llevar un proceso recursivo a uno iterativo, esto puede ser complicado algunas veces y más aún cuando ya se tenga el proceso de manera recursiva implementado, por lo que una solución es tomar dicha implementación y tratarla de manera iterativa dentro de una función, a dicha técnica se le conoce como trampoline. Este término esta relacionado con el lenguaje Lisp, pero se utiliza para identificar dicha técnica. En el siguiente enlace se deja un ejemplo de esto en R.

Finalmente, hay que tener en cuenta que el almacenamiento de llamadas de una función se hace en la Call Stack por que se opera con dichos resultados, por ejemplo en fibonacci(n) se debe realizar fibonacci(n-1)+fibonacci(n-2). Si de alguna manera se implementa un método recursivo sin operar con los resultados previos se podría evitar dicho problema, a esto se le conoce como Tail Call Optimization.