10.5. Pistas

Si estuvo jugando con la función fibonacci de la Sección 5.7, es posible que haya notado que cuanto mas grande es el argumento que le da, mas tiempo le cuesta ejecutarse. Mas aun, el tiempo de ejecución aumenta muy rápidamente.

En nuestra maquina, fibonacci(20) acaba instantáneamente, fibonacci(30) tarda mas o menos un segundo, y fibonacci(40) tarda una eternidad.

Para entender por que, observe este grafico de llamadas de fibonacci con n=4:

Un grafico de llamadas muestra un conjunto de cajas de función con líneas que conectan cada caja con las cajas de las funciones a las que llama. En lo alto del grafico, fibonacci con n=4 llama a fibonacci con n=3 y n=2. A su vez, fibonacci con n=3 llama a fibonacci con n=2 y n=1. Y así sucesivamente.

Cuente cuantas veces se llama a fibonacci(0) y fibonacci(1). Es una solución ineficaz al problema, y empeora mucho tal como crece el argumento.

Una buena solución es llevar un registro de los valores que ya se han calculado almacenándolos en un diccionario. A un valor que ya ha sido calculado y almacenado para un uso posterior se le llama pista. Aquí hay una implementación de fibonacci con pistas:

   1: anteriores = {0:1, 1:1}

   2: def fibonacci(n):

   3:         if anteriores.has_key(n):

   4:             return anteriores[n]

   5:         else:

   6:         nuevoValor = fibonacci(n-1) + fibonacci(n-2)

   7:         anteriores[n] = nuevoValor

   8:         return nuevoValor

El diccionario llamado anteriores mantiene un registro de los valores de Fibonacci que ya conocemos. El programa comienza con solo dos pares: 0 corresponde a 1 y 1 corresponde a 1.

Siempre que se llama a fibonacci comprueba si el diccionario contiene el resultado ya calculado. Si esta ahí, la función puede devolver el valor inmediatamente sin hacer mas llamadas recursivas. Si no, tiene que calcular el nuevo valor. El nuevo valor se añade al diccionario antes de que la función vuelva.

Con esta versión de fibonacci, nuestra maquina puede calcular fibonacci(40) en un abrir y cerrar de ojos. Pero cuando intentamos calcular fibonacci(50), nos encontramos con otro problema:

   1: >>> fibonacci(50)

   2: OverflowError: integer addition

La respuesta, como vera en un momento, es 20.365.011.074. El problema es que este numero es demasiado grande para caber en un entero de Python. Se desborda. Afortunadamente, hay una solución fácil para este problema.