Cuánto va a tardar

Acá vamos a ver algunos métodos que sirven para estimar el tiempo que va a tardar en ejecutarse un programa. Esta estimación se puede hacer antes de ejecutarlo, e incluso antes de escribirlo completamente.

Es importante ya que a veces hay que elegir entre usar un algoritmo sencillo y lento o usar un algoritmo complicado y rápido. Si podemos ver que el algoritmo “lento” va a tardar unos pocos segundos, quizás no valga la pena arruinarse una tarde escribiendo el otro.

En otros casos lo que uno quiere es medir realmente cuánto tarda el programa que ya escribimos y se está ejecutando. Esto es útil para ver si las estimaciones y aproximaciones que hicimos son razonables. Para esto te puede servir la lección “midiendo tiempos” del curso Omanet/CyM98.

Aproximando tiempos

Si uno trata de calcular exactamente cuánto va a demorar un programa, se puede volver loco. Es una tarea muy complicada. Pero en general hay formas fáciles de tener una idea de si un programa va a tardar mucho o poco.

La idea es no sumar el tiempo que tarda cada instrucción. Eso depende de muchas cosas, y hay detalles muy delicados: por ejemplo, las multiplicaciones son mas lentas que las sumas en algunas computadoras, y en otras tardan lo mismo.

Lo que vamos a hacer es contar cuántas veces se ejecuta la instrucción que más se realiza. Usualmente es más o menos fácil darse cuenta cuál es, y es un par de cuentitas ver cuántas veces son.

Fíjense que esto da un par de resultados interesantes. Por ejemplo, vamos a decir que el programa:

a = 10

“tarda 1 paso”, y el programa:
a = 10
a = 20
a = 30
a = 40

también “tarda 1 paso”, aun cuando el segundo es claro que es más lento. Como dije, lo que hacemos es aproximar, no calcular exactamente. Los dos programas de arriba son instantáneos, así que no está tan mal decir que tardan lo mismo (aproximadamente). Aunque esto parece un poco trucho, en la práctica funciona bastante bien. Sucede que en la mayoría de los programas hay un grupo de instrucciones que se ejecutan mucho más veces que las demás, y eso determina el 99% del tiempo total.

Fíjense que lo de “paso” es un nombre que le damos, pero cuando decimos eso nos referimos a cuántas veces se ejecuta la instrucción que más se ejecuta. Más abajo vamos a poner un par de detalles extra de cómo contar.

¿Cuánto es mucho?

Dejemos para luego el problema de cómo contar, y veamos cuánto es “mucho”. Supongamos que tenemos el número N de veces que se ejecuta la instrucción más ejecutada. Podemos hacernos una idea aproximada de si el programa va a tardar mucho o poco:

  • Instantáneo: N < 10000.
  • Un pestañeo: N aproximadamente 100000-1000000 (un millón).
  • Unos pocos segundos: N aproximadamente 1000000-10000000.
  • Segundos o minutos: N aproximadamente 100000000 (cien millones).
  • Minutos, tal vez horas: N aproximadamente 1 a 10 mil millones.
  • Mucho: a partir de 10 mil millones, poco más o menos.

Estos números dependen de la velocidad de la máquina y de cuánto tarda la “instrucción” más ejecutada. En una computadora rápida (2 o 3Ghz) si tal instrucción es rápida y simple esos números pueden ser exagerados. En una computadora más lenta/vieja, o si tal instrucción es una cosa más complicada que lo usual, esos números pueden quedar optimistas.

Contando las instrucciones

Entrada/salida

Las instrucciones para escribir en pantalla en general son un poco lentas, pero las vamos a contar como un solo paso. No importan mucho porque uno a lo sumo imprime menos de 1000 cosas en una solución de problema, y eso es un instante.

Si mientras hacemos el programa éste imprime muchas cosas (miles), eso empieza a frenarlo al programa. Traten de sacarle algunos print (seguramente está mostrando datos innecesarios… 1000 cosas son más de las que ustedes tienen tiempo de leer).

Una cosa a tener en cuenta es que si definen sus propias funciones, y llaman a esa función al imprimir, esa
instrucción de imprimir la vamos a contar como la cantidad de pasos que hace la función de ustedes. Por ejemplo, si definieron una función factorial(n) que tarda ‘n’ pasos, y llaman a print factorial(30), ese print lo vamos a contar como 30 pasos en vez de uno.

Las instrucciones para leer de pantalla son tan lentas como la velocidad que uno tipea (eso es lentísimo), pero normalmente no importa porque o no las usamos, o estan al principio del programa y se ejecutan una vez.

Asignaciones

Las asignaciones son las instrucciones en que uno guarda un valor en una variable (=, ó := según el lenguaje que usen).

a = 2

El valor asignado puede ser el resultado de calcular una expresión:
a = 1998*2008 - 4011982

Si lo que hacen es sacar una cuenta con las operaciones básicas (suma, resta, multiplicación, división, resto, …), cuenta como un paso. Si sólo usan funciones básicas del lenguaje (valor absoluto, raíz cuadrada, logaritmo, coseno, …), también cuenta un paso. En resumen: son rápidas si hacen cualquier cuenta que haga una tecla de una calculadora científica.

Si ustedes definen sus propias funciones, pasa lo mismo que vimos arriba: vamos a contar los pasos de la función como pasos de la asignación. O sea, siguiendo del ejemplo de antes, si hacen a = factorial(55), esa asignación cuenta como 55 pasos.

Bifurcaciones (if)

Acá la cosa se empieza a poner un poco más complicada. Por un lado tenemos la cantidad de pasos que se necesitan para calcular la condición, y por otro las dos posibilidades (según si la condición se cumple o no).

La cantidad de pasos de la condición se calcula como en las asignaciones. Cuenta como 1 para operaciones básicas (eso incluye las comparaciones '<','>', '==', etc. y los operadores lógicos). Si usan funciones ahí adentro, es lo que tarden las funciones.

La complicación viene en que cuando queremos contar las instrucciones de adentro no sabemos si van a ejecutarse 0 veces o 1 vez (depende de si la condición era verdadera o falsa). Se puede hacer una estimación razonable con un poco de buen criterio. Si sabemos que una rama se ejecuta mucho más que la otra, contamos el if como la cantidad de pasos de la rama que más se ejecuta. Si las dos son más o menos lo mismo, o no sabemos, podemos tomar la más grande.

Una cosa a tener en cuenta, es que si la condición tarda lo mismo o más que las dos ramas del if, no hace falta preocuparse cual de las ramas nos interesa más, porque igual nos interesa más la condición que las ramas.

Ciclos for

Acá la cosa se pone interesante. Cuando queremos ver cuántos pasos hace un pedazo de programa:

for i = 1 to N
    XXXX  ' hacer algo dentro del for
next

lo que hacemos es ver cuántos pasos hace 'XXXX' sin el for, y multiplicamos eso por N. por ejemplo, si tenemos algo como:
for i = 1 to 1000
    a = factorial(50)
    print a
next

Nos fijamos primero cuánto tarda la parte de adentro: hay una asignación que llama a una función, y la función hace 50 pasos, así que la asignacón por sí sola (sin mirar el for) hace 50 pasos. El print va a contar como menos pasos, así que no importa. El contendio del for hace 50 pasos. Pero, como eso está dentro de un for que hace 1000 “vueltas”, multiplicamos por 1000, y tenemos que el programita tarda 50.000 “pasos”.

Las cuentas se pueden poner complicadas. Por ejemplo, podríamos tener algo como:

for i = 1 to 1000
    print factorial(i)
next

Ahora ya no podemos ver cuánto tarda la parte de adentro por sí sola, ya que depende de i. Una cosa que podemos hacer de forma rápida es ver que i a veces es chiquito, y otras veces es grande. Entonces tomamos como que adentro del for vale siempre el promedio de las dos puntas: $(1000+1) / 2 = 500,5$. Estimamos entonces que el contenido del for tarda 500,5 pasos por sí solo, así que al estar dentro de un for de mil vueltas tarda 500.500 (quinientos mil quinientos) pasos. O si queremos hacer menos cuentas, simplemente tomamos el peor caso: el contenido tarda 1000 pasos (en vez de 500). Apenas le erramos por un 2…

Otra opción es ponerse a hacer las cuentas más en detalle, pero en general para CyM no vale la pena. Igual lo pueden hacer en sus casas, como lindo ejercicio de matemática. Por ejemplo, para este caso, nos podemos fijar que la parte de adentro va a tardar primero 1 paso, después 2, después 3… y así hasta 1000. Lo que queremos calcular es en realidad $1+2+3+4+...+1000$. Si leyeron la parte de combinatoria y la de sumatorias van a ver que esto da 500.500, que es exactamente lo mismo que nuestra primera estimación a ojo.

Estimar así a ojo no siempre da tan preciso, pero normalmente alcanza para hacerse una idea aproximada.

Un ejemplo más complicado podría ser:

for a = 0 to 100
    for b = a to 100
        for c = b to 100 do
            if a+b+c==188 then 
                print a
            end if
        next
    next
next

El condicional (if) es fácil: cuenta como un paso siempre, y se ejecuta más que el print. Dado que es la instrucción que más se ejecuta, veamos cuántas veces lo hace. Tomamos primero el tercer for, y vemos que da 100-b pasos; como depende de b tomamos b como promedio de sus límites a y 100. Pero a también varía, así que lo tomamos como promedio de sus limites, que son 0 y 100. Es decir, contamos el ciclo de b como si fuera de 50 a 100 (51 veces), y el ciclo de c como si fuera entre el promedio de 50 y 100 que es 75. Por lo tanto, el tercer ciclo tarda 26 pasos, al meterlo dentro del segundo multiplicamos eso por 51 (la cantidad de vueltas promedio que da ese ciclo) y nos queda $26 \cdot 51$, y a eso lo metemos dentro del primer ciclo que da 101 vueltas. En total estimamos $26 \cdot 51 \cdot 101 = 133926$ pasos. (Si lo hacemos por el camino del peor caso, nos da $101 \cdot 101 \cdot 101 \approx 1000000$ pasos. Poco más de 5 veces el valor exacto; hasta 10 nos mantiene dentro del mismo “orden de magnitud”.)

Si hacemos la cuenta exacta nos da 176851. Fíjense que esta vez estimamos un poco de menos, pero entramos en la misma categoría de velocidad (un pestañeo).

Otros ciclos (while, repeat)

Estos ciclos, cuando no son equivalentes a un for, suelen ser complicados. Hay que agarrar cada uno y tratar de pensar cuántas vueltas dan. Son todavía más complicados cuando queda uno metido dentro de otro.

Funciones simples

Para calcular cuanto tarda una función, hacemos lo mismo que antes, tomando a la función como si fuera un programita chiquito.

Funciones recursivas

(Sobre funciones recursivas, ver recursión.) Si la función se llama a sí misma, la cosa se pone muy difícil. Requiere bastante matemática. Habría que agregar a CyM-wiki una sección sobre recurrencias, la parte de matemática que estudia eso. En algunos pocos casos es posible al menos aproximar. Cuando pongamos soluciones recursivas lo vamos a tratar de poner.

Puntuación: +1+x
Si no se indica lo contrario, el contenido de esta página se ofrece bajo Creative Commons Attribution-Noncommercial-Share Alike 2.5 License.