El fib recursivo de la clase, llamada por llamada: el árbol se
dibuja por profundidad y las cajas en ámbar son valores que ya se habían calculado, los que la
memoización se ahorra. Antes de ver cada número escríbalo; al final, cuatro filas reales de
cProfile sobre ruta.py para decidir qué función se toca primero y qué
tiempo va al informe.
1. El árbol de fib(n)
1def fib(n):
2 if n <= 1:
3 return n
4 else:
5 return fib(n - 1) + fib(n - 2)
5
Cada fila es una profundidad de la recursión y cada caja una llamada, en
el orden en que Python las hace: primero fib(n - 1) hasta el fondo y después fib(n - 2). Una
caja en ámbar es un valor de n que ya se había calculado antes. Corra n = 4 y n = 5 completos
antes de pasar a la carta siguiente.
2. Antes de mover n
¿Cuántas llamadas a fib hace fib(6)? La primera también
cuenta.
n
Llamadas a fib
Veces la de n − 1
3. Con memoización
1from functools import lru_cache
2
3@lru_cache(maxsize=None)
4def fib(n):
5 if n <= 1:
6 return n
7 else:
8 return fib(n - 1) + fib(n - 2)
Con memoización, ¿cuántas llamadas ejecutan el cuerpo de fib para
fib(6)?
fib(6)
fib(35)
sin memo
con memo
sin memo
con memo
Las cifras del reporte son las de la corrida de la clase con fib(35);
fib(6) no se midió. Los 4,957 s cargan el costo del perfilador: sin él, ese fib(35) corre
cerca de 3,5 s, entre un 30 y un 45 % menos.
4. Leer la tabla de cProfile
ruta.py busca, para cada uno de dos mil puntos, la
distancia a su vecino más cercano; antes espera medio segundo a un sensor. Cuatro filas de
python3 -m cProfile -s cumulative ruta.py:
El encabezado dice 2,963 s. Sin perfilador,
time dio 1,382 s. ¿Qué número va en el informe?
tottime es lo que la función gasta por su cuenta; cumtime le suma lo que
gastan las funciones que ella llama. Por eso el cumtime de mas_cercano contiene el de
distancia, y el de distancia contiene el de sqrt.