Minimiza la complejidad temporal de tus algoritmos

Nunca se ha preguntado por qué si la capacidad de procesamiento del hardware de nuestros dispositivos electrónicos ha ido siempre en aumento, aún existen programas, sitios web, utilitarios, etc. que funcionan desesperadamente lentos. La respuesta, en muchos casos, pudiera ser: los programadores adoramos malgastar y consumir todo el hardware y dedicamos poco tiempo a minimizar la complejidad temporal de nuestro código.

En este post les quiero hablar acerca de cómo nuestra irresponsabilidad como codificadores afecta los tiempos de ejecución de algoritmos que escribimos decenas de veces en cualquier proyecto. En nuestras manos está ser un “buen programador” o simplemente un “programador”. Por supuesto, no somos perfectos y al mejor escribano se le va un borrón, sin embargo, sí debemos buscar la perfección del software que desarrollamos.

Como programadores tenemos la responsabilidad de usar de forma eficiente los recursos físicos y de brindar al usuario la mejor experiencia posible frente al ordenador. Esto significa que debemos lograr que el tiempo de espera entre una acción sobre una interfaz gráfica o línea de comandos y la respuesta del software sea el mínimo.

Aunque se sabe que, en los períodos de respuesta de las aplicaciones web, por ejemplo, influyen otros factores que escapan de nuestras manos, como verán podemos cumplir al menos con la parte que nos toca teniendo en cuenta conceptos muy básicos. Se puede decir que realizando las sencillas acciones que describiré a continuación estaremos disminuyendo la complejidad temporal del algoritmo en cuestión.

Cuando estamos iterando con un for sobre un arreglo, por ejemplo, vale la pena pre-calcular la cantidad de iteraciones y reducir prácticamente el tiempo de ejecución a la mitad. Aquí les dejo un código de ejemplo escrito en PHP:

<?php 	
	/*
	Crear un arreglo con datos cualesquiera.
	Uso un número muy grande para que la diferencia de tiempo sea visible.
	*/
	$myarray = [];
	for($i = 0; $i < 900000; $i++)
	{
		$myarray[] = $i;
	}		
	
	/*
	Prueba 1: Recorrer todo el arreglo sin antes pre-calcular su tamaño.
	Notese que en cada iteracion del for se calcula una y otra vez el tamaño del arreglo: count($myarray);
	desperdiciando ciclos de procesador
	*/
	
	//Inicio del script
	$start = microtime(true);	
	
	for($i = 0; $i < count($myarray); $i++)
	{
		//Realizar cualquier accion...
		$lower = strtolower("Hola mundo!");
	}
		
	//Fin del script
	$end = microtime(true);
	//Calcular el tiempo que demoro la ejecucion del script
	$elapsed = round($end - $start, 2);	
	echo "Tiempo transcurrido sin pre-calcular la cantidad de elementos del arreglo: $elapsed. ";
	
	
	//Prueba 2: Pre-calcular solo una vez el tamaño del arreglo antes del bucle for: $counter = count($myarray);
	
	//Inicio del script
	$start = microtime(true);
	
	$counter = count($myarray);
	
	for($i = 0; $i < $counter; $i++)
	{
		//Realizar la misma accion de la prueba 1
		$lower = strtolower("Hola mundo!");
	}
		
	//Fin del script
	$end = microtime(true);
	//Calcular el tiempo que demoro la ejecucion del script
	$elapsed = round($end - $start, 2);	
	echo "Tiempo transcurrido pre-calculando la cantidad de elementos del arreglo: $elapsed.";
?> 

Si usted realiza la prueba verá que pre-calcular el tamaño del arreglo (Prueba 2) hace que nuestro script se ejecute más rápido. ¿Por qué sucede así? Porque en la prueba número uno, cada vez que se evalúa la condición $i <count($myarray); se está calculando una y otra vez el tamaño del arreglo $myarray en vano, teniendo en cuenta que el mismo no cambia. En cambio, en la prueba dos, solo lo calculamos una vez. Usted puede decir que si el arreglo es pequeño la diferencia es imperceptible y es cierto, pero no es menos cierto que la mayoría de las veces que necesitamos una estructura repetitiva como un for o un while no sabemos por anticipado la cantidad de elementos.

Otro ejemplo muy sencillo puede ser cuando estamos realizando una búsqueda lineal en un arreglo para encontrar un elemento X. La práctica que les recomiendo es interrumpir el bucle una vez que se ha cumplido la condición establecida, miren este ejemplo:

<?php 	
	/*
	Crear un arreglo con datos cualesquiera.
	Uso un número muy grande para que la diferencia de tiempo sea visible.
	*/
	$myarray = [];
	for($i = 0; $i < 900000; $i++)
	{
		$myarray[] = $i;
	}		
	
	/*
	Prueba 1: Recorrer el arreglo en busca del elemento deseado, en este caso 450000, que esta a la mitad del arreglo.
	Note que aun despues de encontrar el elemento deseado el bucle for continuara hasta 900000.
	Note ademas que continuo sin pre-calcular el tamaño del arreglo para juntar las dos malas practicas
	*/
	
	//Inicio del script
	$start = microtime(true);	

	for($i = 0; $i < count($myarray); $i++)
	{
		//Buscar el elemento deseado
		if($myarray[$i] == 450000){
			$item = $myarray[$i];
		}
	}
		
	//Fin del script
	$end = microtime(true);
	//Calcular el tiempo que demoro la ejecucion del script
	$elapsed = round($end - $start, 2);	
	echo "Tiempo transcurrido sin interrumpir el bucle: $elapsed. ";
	
	
	//Prueba 2: Interrumpir el bucle for una vez que se ha encontrado el elemento deseado
	
	//Inicio del script
	$start = microtime(true);
	
	$counter = count($myarray);	
	for($i = 0; $i < $counter; $i++)
	{
		//Buscar el elemento deseado
		if($myarray[$i] == 450000){
			$item = $myarray[$i];
			//Interrumpir el bucle for
			$i = $counter;
		}
	}
		
	//Fin del script
	$end = microtime(true);
	//Calcular el tiempo que demoro la ejecucion del script
	$elapsed = round($end - $start, 2);	
	echo "Tiempo transcurrido interrumpiendo el bucle: $elapsed.";
?> 

¿Qué sucede aquí? En la prueba uno, después de encontrar el elemento que se busca, continuamos malgastando ciclos de procesador. Fíjense también que sigo sin pre-calcular el tamaño del arreglo con toda la intención de mostrar qué sucede al unir las dos malas prácticas; el segundo es varias veces más rápido que el primero. En el segundo ejemplo al encontrar el valor deseado interrumpo el bucle haciendo $i = $counter;. De esta forma el mejor de los casos será cuando el elemento buscado es el primero y el peor cuando es el último en la colección de datos, pero siempre nos aseguramos de no malgastar nuestro tiempo una vez que cumplimos nuestro objetivo.

Hemos visto estos ejemplos en PHP aunque los consejos son válidos para cualquier lenguaje de programación. Si le interesó el tema y quiere profundizar más específicamente en optimizar su código PHP visite PHPBench.

Existen interminables ejemplos como estos, yo solo quería despertar su curiosidad, ojalá lo haya logrado.