Calcular tiempos de ejecución, en Python

Hola. Una forma rápida y sencilla de evaluar un algoritmo es calcular el tiempo de ejecución del mismo, para ver si efectivamente es óptimo para nuestros intereses. Este tipo de análisis puede hacerse matemáticamente, ó si disponemos de algún "proceso" que nos indique la rapidez del mismo. No voy a entrar aquí sobre como calcular tiempos de ejecución O, Omega y demás cosas de estas. En este post vamos a ver la forma de calcular el tiempo de ejecución, en segundos, para cualquier algoritmo. Para nuestro ejemplo, mediremos el algoritmo de ordenación QuickSort.

Lo que vamos a crear es, mediante una función decoradora, una función para calcular tiempos de ejecución. Nuestra función de medición es la siguiente:

def cronometro(funcion):
   def funcion_a_ejecutar(*argumentos):
       # Tiempo de inicio de ejecución.
       inicio = time.time()
       # Lanzamos función a ejecutar.
       ret = funcion(*argumentos)
       # Tiempo de fin de ejecución.
       fin = time.time()
       # Tiempo de ejecución.
       tiempo_total = fin - inicio
       # Devolvemos el tiempo de ejecución.
       return tiempo_total
   # Devolvemos la función que se ejecuta.
   return funcion_a_ejecutar

Para ver como funciona vamos a crear una lista de números, creados aleatoriamente (para ello vamos a utilizar del módulo random, uniform). El código es el siguiente:

def funcion_generica():
   lista_numeros = []
   for i in range(1,100000):
       numero = int(random.uniform(0,500))
       lista_numeros.append(numero)
   # Devolvemos lista de números aleatorios.
   return lista_numeros

De esta manera lo que vamos a hacer ordenar dicha lista, en varios tipos de clasificación (ascendente y descendente), esto es, vamos a medir el tiempo que tarda el algoritmo QuickSort en realizar dicha tarea. Así la implementación de este algoritmo de clasificación QuickSort es el siguiente:

def quicksort(datos, primero, ultimo, ordenacion = 'asc'):
       '''
       Método que implementa el algoritmo QuickSort. Utilizado
       para clasificación de filas.
       '''
       i = primero
       j = ultimo
       posicion_pivote = (primero + ultimo) / 2
       pivote = datos[posicion_pivote]
       while i <= j:
           if ordenacion == 'asc':
               while datos[i] < pivote: i+=1
               while datos[j] > pivote: j-=1
           if ordenacion == 'desc':
               while datos[i] > pivote: i+=1
               while datos[j] < pivote: j-=1
           if i <= j:
               aux = datos[i]
               datos[i] = datos[j]
               datos[j] = aux
               i+=1
               j-=1
       if primero < j:
           datos = quicksort(datos, primero, j, ordenacion)
       if ultimo > i:
           datos = quicksort(datos, i, ultimo, ordenacion)
       return datos

Antes de todo hay que importar los módulos necesarios, esto es:

import time
import random

Por último, solo nos falta ejecutar las funciones definidas. Lo primero que hacemos es generar una lista de números aleatorios:

lista_numeros = funcion_generica()

Seguidamente, mediante la función decoradora definida previamente, ordenamos mediante QuickSort, de manera que se mida el tiempo de ejecución.

tiempo1 = cronometro(quicksort)(lista_numeros,0,99998)

Ahora ordenamos con QuickSort, en ordenación descendente, con una lista previamente ordenada ascendente.

tiempo2 = cronometro(quicksort)(lista_numeros,0,99998,'desc')

Y ordenamos con QuickSort, en ordenación ascendente, con una lista previamente ordenada descendente.

tiempo3 = cronometro(quicksort)(lista_numeros,0,99998)

Finalmente vemos el cálculo total de tiempos del algoritmo QuickSort.

print "Cálculo total de tiempos del algoritmo QuickSort"
print "Se ordena una lista de 99999 elementos."
print ""
print "Lista no ordenada: ", tiempo1, " segundos"
print "Lista ordenada ascendente: ", tiempo2, " segundos"
print "Lista ordenada descendente: ", tiempo3, " segundos"

Los resultados que me han dado son los siguientes:


Saludos.