En algunas ocasiones preocuparse por la eficiencia de un algoritmo es la diferencia entre encontrar una solución y no encontrarla. Disponer de un algoritmo que nos ofrece una solución en un tiempo imposible de asumir, es no haber encontrado la solución en absoluto. En algunos casos, cuando el tiempo no es determinante, podemos ser menos sutiles y usar la "fuerza bruta", siempre y cuando el tiempo que necesita nuestro programa para ejecutarse sea razonable. Son soluciones que, aunque poco elegantes, nos permiten seguir avanzando. No obstante evaluar nuestros algoritmos es una buena practica que permite mejorar los mismos, encontrando soluciones mas óptimas y mejorando el rendimiento. En Python tenemos algunas herramientas muy útiles, describiremos algunas y como se pueden usar:
- Para evaluar tiempos tenemos timing, su uso resulta muy sencillo:
Una forma de uso muy útil de timing es desde la línea de comandos, un ejemplo para evaluar una función que se encuentra en un módulo (mymodule) podría realizarse como $python -m timeit -s "import mymodule as m" "m.function()"
- Para comparar funciones o encontrar cuellos de botella, cProfile.
import cProfile
def main ():
def factorial1(n):
if n == 0:
return 1
return factorial1(n-1)*n
def factorial2(n):
fac = 1
for x in xrange(1,n+1):
fac = fac * x
return fac
def factorial3(n):
fac = 1
for x in range(1,n+1):
fac = fac * x
return fac
factorial1(990)
factorial2(990)
factorial3(990)
if __name__=="__main__":
main()
cProfile.run('main()')
El resultado que ofrece mi máquina es el siguiente:
Como puede verse el cuello de botella se encuentra en la función recursiva (factorial1). Para poder evaluar con más precisión cual de las funciones es más efectiva, debemos aumentar el límite de profundidad de recursividad, ya que factorial1 estará limitado a 950. Para aumentar tal restricción añadimos lo siguiente:
import sys sys.setrecursionlimit(10000)
Ahora podemos calcular el factorial de un número mucho más grande, digamos 5000. El resultado es:
Se confirma el cuello de botella en la función recursiva resultando ganadora aquella que emplea range en lugar de xrange. Ya que estamos, aprovechemos para comprobar que es más rápido en una lista; append vs insert.
def main2():
def append():
list1 = []
for x in range(1,1000):
list1.append(x)
def insert():
list1 = []
for x in range(1,1000):
list1.insert(0,x)
append()
insert()
if __name__=="__main2__":
main2()
cProfile.run('main2()')
Los resultados del combate:
Como puede verse el método append resulta ser más efectivo que insert.
Estas herramientas, y algunas otras, son muy efectivas a la hora de valorar los distintos algoritmos. Si se quiere ser preciso estos experimentos deberían realizarse muchas veces y con distintos tamaños o repeticiones. Por ejemplo, en el experimento anterior, insert es igual de rápido que append para pocas inserciones, sin embargo cuando estas ganan en tamaño es cuando las diferencias se hacen más notables. Visualizar los resultados mediante gráficas para poder valorar mejor los resultados también es muy importante. Python ofrece herramientas eficientes para automatizar y ofrecer estos resultados o elaborar informes, no obstante este propósito excede de la finalidad de esta entrada, pero basta decir que los módulos csv y
matplotlib aportan las herramientas necesarias para tal labor .
No hay comentarios:
Publicar un comentario