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:

[pastacode lang=”php” manual=”%3C%3Fphp%20%09%0A%09%2F*%0A%09Crear%20un%20arreglo%20con%20datos%20cualesquiera.%0A%09Uso%20un%20n%C3%BAmero%20muy%20grande%20para%20que%20la%20diferencia%20de%20tiempo%20sea%20visible.%0A%09*%2F%0A%09%24myarray%20%3D%20%5B%5D%3B%0A%09for(%24i%20%3D%200%3B%20%24i%20%3C%20900000%3B%20%24i%2B%2B)%0A%09%7B%0A%09%09%24myarray%5B%5D%20%3D%20%24i%3B%0A%09%7D%09%09%0A%09%0A%09%2F*%0A%09Prueba%201%3A%20Recorrer%20todo%20el%20arreglo%20sin%20antes%20pre-calcular%20su%20tama%C3%B1o.%0A%09Notese%20que%20en%20cada%20iteracion%20del%20for%20se%20calcula%20una%20y%20otra%20vez%20el%20tama%C3%B1o%20del%20arreglo%3A%20count(%24myarray)%3B%0A%09desperdiciando%20ciclos%20de%20procesador%0A%09*%2F%0A%09%0A%09%2F%2FInicio%20del%20script%0A%09%24start%20%3D%20microtime(true)%3B%09%0A%09%0A%09for(%24i%20%3D%200%3B%20%24i%20%3C%20count(%24myarray)%3B%20%24i%2B%2B)%0A%09%7B%0A%09%09%2F%2FRealizar%20cualquier%20accion…%0A%09%09%24lower%20%3D%20strtolower(%22Hola%20mundo!%22)%3B%0A%09%7D%0A%09%09%0A%09%2F%2FFin%20del%20script%0A%09%24end%20%3D%20microtime(true)%3B%0A%09%2F%2FCalcular%20el%20tiempo%20que%20demoro%20la%20ejecucion%20del%20script%0A%09%24elapsed%20%3D%20round(%24end%20-%20%24start%2C%202)%3B%09%0A%09echo%20%22Tiempo%20transcurrido%20sin%20pre-calcular%20la%20cantidad%20de%20elementos%20del%20arreglo%3A%20%24elapsed.%20%22%3B%0A%09%0A%09%0A%09%2F%2FPrueba%202%3A%20Pre-calcular%20solo%20una%20vez%20el%20tama%C3%B1o%20del%20arreglo%20antes%20del%20bucle%20for%3A%20%24counter%20%3D%20count(%24myarray)%3B%0A%09%0A%09%2F%2FInicio%20del%20script%0A%09%24start%20%3D%20microtime(true)%3B%0A%09%0A%09%24counter%20%3D%20count(%24myarray)%3B%0A%09%0A%09for(%24i%20%3D%200%3B%20%24i%20%3C%20%24counter%3B%20%24i%2B%2B)%0A%09%7B%0A%09%09%2F%2FRealizar%20la%20misma%20accion%20de%20la%20prueba%201%0A%09%09%24lower%20%3D%20strtolower(%22Hola%20mundo!%22)%3B%0A%09%7D%0A%09%09%0A%09%2F%2FFin%20del%20script%0A%09%24end%20%3D%20microtime(true)%3B%0A%09%2F%2FCalcular%20el%20tiempo%20que%20demoro%20la%20ejecucion%20del%20script%0A%09%24elapsed%20%3D%20round(%24end%20-%20%24start%2C%202)%3B%09%0A%09echo%20%22Tiempo%20transcurrido%20pre-calculando%20la%20cantidad%20de%20elementos%20del%20arreglo%3A%20%24elapsed.%22%3B%0A%3F%3E%20″ message=”” highlight=”” provider=”manual”/]

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:

[pastacode lang=”php” manual=”%3C%3Fphp%20%09%0A%09%2F*%0A%09Crear%20un%20arreglo%20con%20datos%20cualesquiera.%0A%09Uso%20un%20n%C3%BAmero%20muy%20grande%20para%20que%20la%20diferencia%20de%20tiempo%20sea%20visible.%0A%09*%2F%0A%09%24myarray%20%3D%20%5B%5D%3B%0A%09for(%24i%20%3D%200%3B%20%24i%20%3C%20900000%3B%20%24i%2B%2B)%0A%09%7B%0A%09%09%24myarray%5B%5D%20%3D%20%24i%3B%0A%09%7D%09%09%0A%09%0A%09%2F*%0A%09Prueba%201%3A%20Recorrer%20el%20arreglo%20en%20busca%20del%20elemento%20deseado%2C%20en%20este%20caso%20450000%2C%20que%20esta%20a%20la%20mitad%20del%20arreglo.%0A%09Note%20que%20aun%20despues%20de%20encontrar%20el%20elemento%20deseado%20el%20bucle%20for%20continuara%20hasta%20900000.%0A%09Note%20ademas%20que%20continuo%20sin%20pre-calcular%20el%20tama%C3%B1o%20del%20arreglo%20para%20juntar%20las%20dos%20malas%20practicas%0A%09*%2F%0A%09%0A%09%2F%2FInicio%20del%20script%0A%09%24start%20%3D%20microtime(true)%3B%09%0A%0A%09for(%24i%20%3D%200%3B%20%24i%20%3C%20count(%24myarray)%3B%20%24i%2B%2B)%0A%09%7B%0A%09%09%2F%2FBuscar%20el%20elemento%20deseado%0A%09%09if(%24myarray%5B%24i%5D%20%3D%3D%20450000)%7B%0A%09%09%09%24item%20%3D%20%24myarray%5B%24i%5D%3B%0A%09%09%7D%0A%09%7D%0A%09%09%0A%09%2F%2FFin%20del%20script%0A%09%24end%20%3D%20microtime(true)%3B%0A%09%2F%2FCalcular%20el%20tiempo%20que%20demoro%20la%20ejecucion%20del%20script%0A%09%24elapsed%20%3D%20round(%24end%20-%20%24start%2C%202)%3B%09%0A%09echo%20%22Tiempo%20transcurrido%20sin%20interrumpir%20el%20bucle%3A%20%24elapsed.%20%22%3B%0A%09%0A%09%0A%09%2F%2FPrueba%202%3A%20Interrumpir%20el%20bucle%20for%20una%20vez%20que%20se%20ha%20encontrado%20el%20elemento%20deseado%0A%09%0A%09%2F%2FInicio%20del%20script%0A%09%24start%20%3D%20microtime(true)%3B%0A%09%0A%09%24counter%20%3D%20count(%24myarray)%3B%09%0A%09for(%24i%20%3D%200%3B%20%24i%20%3C%20%24counter%3B%20%24i%2B%2B)%0A%09%7B%0A%09%09%2F%2FBuscar%20el%20elemento%20deseado%0A%09%09if(%24myarray%5B%24i%5D%20%3D%3D%20450000)%7B%0A%09%09%09%24item%20%3D%20%24myarray%5B%24i%5D%3B%0A%09%09%09%2F%2FInterrumpir%20el%20bucle%20for%0A%09%09%09%24i%20%3D%20%24counter%3B%0A%09%09%7D%0A%09%7D%0A%09%09%0A%09%2F%2FFin%20del%20script%0A%09%24end%20%3D%20microtime(true)%3B%0A%09%2F%2FCalcular%20el%20tiempo%20que%20demoro%20la%20ejecucion%20del%20script%0A%09%24elapsed%20%3D%20round(%24end%20-%20%24start%2C%202)%3B%09%0A%09echo%20%22Tiempo%20transcurrido%20interrumpiendo%20el%20bucle%3A%20%24elapsed.%22%3B%0A%3F%3E%20″ message=”” highlight=”” provider=”manual”/]

¿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.

Leave a Reply

Your email address will not be published. Required fields are marked *