← Volver a los ejercicios

Cuántas veces se llama fib y qué cuenta cProfile

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.

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 memocon memosin memocon 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:

8004232 function calls in 2.963 seconds
ncalls tottime percall cumtime percall filename:lineno(function)
2000 0.786 0.000 2.461 0.001 ruta.py:9(mas_cercano)
4000000 1.232 0.000 1.675 0.000 ruta.py:5(distancia)
1 0.500 0.500 0.500 0.500 {built-in method time.sleep}
4000000 0.443 0.000 0.443 0.000 {built-in method math.sqrt}

¿Qué función conviene tocar primero?

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.