Diccionarios, recursión, y Fibonacci

5 minutos de lectura

Un arreglo asociativo -o más comúnmente llamado mapa o diccionario-, es un tipo de dato abstracto.

Está compuesto por una colección de pares (clave, valor).

La clave de cada par debe ser única en todo el diccionario, pero el valor puede estar repetido.

La mayoría de lenguajes cuenta con diccionarios de manera primitiva, o con la inclusión de librerías. Puedes consultar una lista comparativa en Wikipedia.

Los diccionarios tienen varias aplicaciones importantes, incluyendo los patrones de diseño de decorador y memoización.

Memoización

La memoización es un patrón de diseño de software que puede acelerar la ejecución de programas.

Consiste en «recordar» los resultados computados anteriormente. Así, cuando esos resultados quieran usarse de nuevo, no será necesario calcularlos otra vez, sólo se recupera la versión almacenada.


Para poder ejemplificar el uso de los diccionarios y el patrón de memoización, los utilizaré para mejorar esta función fib.

Este algoritmo es ineficiente, pues el número de recursiones que tiene que hacer aumenta increíblemente rápido.

Por ejemplo, si queremos calcular fib(6), las llamadas recursivas se verán algo así:

Tanto fib(5) como fib(6) son llamados sólo una vez, pero fib(4) dos veces, y fib (3) tres.

Diccionarios

Para optimizar este algoritmo vamos a utilizar un diccionario. Éste contendrá todos los números de Fibonacci de 1 a n.

Sabemos que fib(1) = 1, y fib(2) = 1. Por lo tanto, nuestro diccionario inicial lucirá algo así:

computed_fib = {1:1, 2:1}

Para que podamos consultar el diccionario dentro de la función fib(), necesitamos recibir el diccionario. Así que tenemos que cambiar nuestra definición:

def fib(n, computed_fib):

también hay que escribir una manera de

a) revisar si el número que buscamos ya existe en el diccionario

if n in computed_fib:
return computed_fib[n]

b) calcularlo y añadirlo al diccionario (si no existe)

nth_fib = fib(n - 1, computed_fib) + fib(n - 2, computed_fib)
computed_fib[number] = nth_fib
return nth_fib

Mutabilidad

Al final, fib queda definida de esta manera:

¡Mucho mejor! Pero habría un problema con esta definición: tenemos que cambiar la manera en la que invocamos la función, ya que recibe dos argumentos.

Específicamente, tendríamos que llamarla enviando un diccionario conteniendo al menos los casos base.

fib(6, {1:1, 2:2})

Y eso puede traer problemas, como enviar un diccionario inválido. Además se ve feo.

Para arreglarlo, vamos a hacer que computed_fib sea recibido con un valor por defecto.

Esto es: que si no se envía un argumento manualmente, tomará un valor pre-definido.

Podemos definirlo de esta manera:

def fib(n, computed_fib = {1:1, 2:1}):

pero es considerado una pésima práctica por algunas cosas oscuras y truculentas de los objetos mutables.

así que mejor lo predeterminamos en None, y lo creamos después:

def fib(n, computed_fib = None):
if computed_fib is None:
computed_fib = {1:1, 2:1}

Así podremos llamar fib(n) y fib(n, dict) sin problema alguno.

Estadísticas


tl;dr: Al calcular el 40-ésimo término, la recursión pura hace más de 200 millones de llamadas en 51s. Con memoización, 77 llamadas en 0.00s


Veamos algunas estadísticas sobre el número de llamadas recursivas, y el tiempo de ejecución de cada algoritmo:

Nota: Originalmente planeé calcular todos los números de fib(1) a fib(100). Con esto no hablo de calcular fib(100), sino de calcular fib(1), y luego fib(2), y luego fib(3), etc…

for i in range(1, 101):
    stats(fib(i))

Sin embargo, pasadas poco más de dos horas, decidí interrumpir el programa. Y para enterarme que sólo había calculado hasta fib(48). ¡Y había tardado 49 minutos sólo en ese último!

Pero perdí los dos archivos .csv que había generado al re-ejecutar el programa con un número más pequeño sin respaldar los dos archivos creados al principio.

De cualquier forma, re-ejecuté hasta fib(40), y aún ahí se puede ver la enorme diferencia entre ambos algoritmos.

El número de llamadas recursivas por algoritmo es:

n No-memoización Memoización
1 1 1
2 1 1
3 3 3
. . .
38 78,176,337 73
39 126,491,971 75
40 204,668,309 77

Y el tiempo de ejecución (en segundos) de cada uno:

n No-memoización Memoización
1 0.0000 s 0.0000 s
2 0.0000 s 0.0000 s
3 0.0000 s 0.0000 s
. . .
38 20.2371 s 0.0000 s
39 32.7778 s 0.0000 s
40 53.0221 s 0.0000 s

Con esto queda claro que la memoización es un patrón de diseño excelente en casos como este.

OK, AQUÍ LAS COSAS SE EMPIEZAN A TORNAR UN POCO OSCURAS, TODO ESTO ERA INNECESARIO, PERO AÚN ASÍ LO ESCRIBÍ. y peor aún: aún así lo publiqué.

Pero no importa si no pude recuperar el 49no número en la secuencia de Fibonacci, por que podemos hacer una estimación con los datos que tenemos.

Tanto el número de llamadas recursivas como el tiempo de ejecución de la implementación recursiva, se comportan como la secuencia de Fibonacci.

Las llamadas pueden calcularse de manera exacta. El tiempo no.

En concreto:

n_llamadas(n) = n_llamadas(n-1) + n_llamadas(n-2) + 1
tiempo(n) =~ tiempo(n-1) + tiempo(n-2)

El problema serían los casos base, pero creo que con utilizar los últimos dos datos registrados bastará.

Para eso sólo llamaremos a la función enviando nuestros propios diccionarios.

Así que veamos qué tantas llamadas y tiempo haría para calcular 1000 números fibonacci:

fib(1000) haría…

86, 933, 115, 373, 874, 912, 871, 377, 055, 350, 081, 251, 605, 129, 321, 034, 743, 560, 804, 963, 458, 179, 073, 110, 835, 898, 103, 780, 807, 759, 680, 158, 510, 338, 591, 845, 186, 160, 645, 269, 550, 419, 379, 246, 479, 746, 644, 942, 323, 285, 992, 881, 813, 066, 375, 876, 597, 939, 299, 857, 032, 007, 408, 952, 275, 590, 333, 698, 457, 749

llamadas en, aproximadamente,

22, 368, 247, 025, 775, 198, 923, 204, 500, 838, 004, 838, 905, 889, 316, 192, 143, 756, 994, 318, 944, 191, 936, 469, 718, 811, 583, 554, 057, 695, 250, 902, 151, 169, 111, 265, 234, 166, 779, 627, 076, 117, 356, 815, 012, 808, 335, 317, 548, 081, 991, 314, 018, 847, 704, 591, 467, 486, 307, 969, 223, 542, 098, 027, 384, 185, 813, 172

segundos.

O 86.933 x10^205 llamadas en 22.368 x10^199

O 86 69-illones de llamadas en 22 67-illones de segundos.

¿cuánto son 22 67-illones de segundos? Bueno, más o menos 709 64-illones de años.

Considerando que la estimación de la edad de la tierra es de 4,540,000,000 años, son como 156 62-illones de vidas-tierra.