Optimizando código

Recientemente he tenido que hacer un programa en el que se tenían que unir cadenas separadas por un espacio. Esto es una chorrada de código, ya lo sé, pero me han venido a la cabeza un par de cosas que el buen programador tiene que tener en la cabeza. El único problema de esta función es que tiene que añadir un espacio entre los diferentes elementos del array salvo al final. Esto nos hace que tengamos un código como el que sigue (supongamos que hay "npalabras" y el array que las contiene es "palabras". "cadena" está inicialmente vacío y suponemos también que tiene el tamaño suficiente para contener la cadena resultado):


for (i=0; i < npalabras; ++i)
{
strcat(cadena, palabras[i]);

if (i != npalabras - 1)
strcat(cadena, " ");
}


Este código es perfectamente normal, y de hecho lo he utilizado de formas parecidas yo mismo anteriormente. Sin embago, estudiándolo un poco tenemos varias cuestiones:

1. En cada bucle se hacen dos comparaciones. Una para el bucle y otra para el if. Esto es muy costoso, sobre todo porque se hace una comparación en cada paso del bucle cuando sabemos que sólo se cumple en la última iteración. Los saltos por lo general rompen la estructura de ejecución interna de los procesadores. Sí, ya sé que llevan predictores de saltos, pero hay ocasiones como esta en las que podemos optimizar el código de una forma elegante.
2. Se hace una resta cada iteración para la comparación (npalabras - 1).

Alguien puede decir que el tiempo del strcat comparado con lo otro es ridículo. Y tiene razón, pero en este caso. Aquí estamos viendo la idea general, la optimización. Así que manos a la obra. La siguiente versión:


for (i=0; i < npalabras - 1; ++i)
{
strcat(cadena, palabras[i]);
strcat(cadena, " ");
}
strcat(cadena, palabras[i]);


Ahora, gracias a repetir el código del último bucle podemos optimizarlo. Nótese que después del bucle, la variable "i" tiene el valor correcto para el último strcat. Sin embargo, todavía no me gusta. Tiene un detalle que no me gusta: la comparación se hace en cada bucle y se tiene que calcular en cada bucle la expresión "npalabras - 1". Para mí la mejor solución sería entonces:


register size_t np = npalabras - 1;
for (i=0; i < np; ++i)
{
strcat(cadena, palabras[i]);
strcat(cadena, " ");
}
strcat(cadena, palabras[i]);


Y así colorín colorado hemos optimizado un bucle. Quizá este ejemplo no sea el mejor del mundo, pero ejemplifica que programar no es sólo hacer funcionar un programa. Me encanta la programación y la optimización de código. Iré mostrando más cosas conforme pase el tiempo.

blog comments powered by Disqus