Códigos hash y optimización de software [ES]
Los que nos dedicamos a la programación de software sabemos lo importante que es la optimización de algoritmos para reducir los recursos necesarios para ejecutar un cierto proceso. En este artículo vamos a analizar un caso muy habitual, en el que aplicando una técnica muy sencilla con códigos hash, se obtienen resultados asombrosos.
La optimización de un algoritmo nos proporciona dos beneficios importantes:
- Obtener el resultado del proceso de forma más rápida. Un ejemplo de esto podría ser reducir el tiempo de respuesta de una página web que tiene que hacer muchos cálculos cuando un cliente la solicita.
- Poder ejecutar más procesos simultáneos en un tiempo dado. Un ejemplo de esto podría ser aumentar la cantidad de páginas web que puede mostrar un servidor concreto y así aumentar el número de usuarios concurrentes soportados por dicho servidor.
Optimizar un proceso es algo bastante manual ya que dependiendo de las operaciones que se ejecuten y los subprocesos que se lancen hay que tomar caminos muy diferentes para reducir tiempos. Incluso, hay casos en los que la mejor optimización consiste en replantearte el proceso completo y desarrollarlo de una forma totalmente diferente, pero hay técnicas que son útiles en muchos casos comunes y que conviene tener siempre a mano para usarlas de forma sistemática al programar. Este es el caso del uso de códigos hash en procesos repetitivos y que es de lo que trataremos en este artículo.
Versión inicial
Planteemos un caso hipotético muy habitual, los bucles anidados. Supongamos que tenemos un listado de usuarios y que cada uno de ellos puede tener libros asociados a él, por ejemplo, en los préstamos de una biblioteca. Ahora supongamos que nos piden un listado con todos los libros, mostrando a cada uno de ellos el usuario que está asociado. Para resolver este caso, se podría plantear el siguiente algoritmo estándar (yo lo presentaré en lenguaje java pero lógicamente se puede extrapolar a cualquier lenguaje de programación):
public void showBooks(ArrayList<BookBean> books, ArrayList<UserBean> users)
{
for (BookBean book : books)
{
UserBean userFound = null;
for (UserBean user : users)
{
if (book.getUserId() == user.getUserId())
{
userFound = user;
break;
}
}
System.out.println(book.getName() + " -> " + user.getName());
}
}
Explicación de la versión inicial
En este algoritmo vemos como se ejecutan dos bucles "for" anidados donde en el primero recorremos los libros que tiene la biblioteca y en el segundo, para cada libro, recorremos los usuarios hasta encontrar el usuario asociado al libro. Con este algorimo, si tenemos 10.000 libros y 1.000 usuarios, por ejemplo, el número de iteraciones sería de:
10.000 (libros) x 1.000 (usuarios) = 10.000.000
Es cierto que el uso de la sentencia break hace que cuando encontremos un usuario de un libro ya no sigamos buscando en el resto de usuarios para ese libro lo que hace que se pueda decir que el número de iteraciones del bucle interno sea de aproximadamente la mitad, es decir, que estamos aplicando una primera optimización donde el número de iteraciones totales sería de:
10.000 (libros) x 500 (usuarios medios con break) = 5.000.000
Ahora el objetivo es reducir ese número de iteraciones y para esto podemos aprovecharnos de los códigos hash, esos mismos códigos hash que habréis escuchado mencionar como uno de los pilares que hacen funcionar nuestras queridas blockchains. Un código hash se puede entender como un "resumen" de una cierta información, y todos sabemos que es más fácil buscar algo en un resumen que en la información completa. En otro artículo hablaré con más detalle de los códigos hash, de como funcionan y de que, sin ser conscientes, nuestros cerebros usan este concepto de forma habitual en nuestra vida cotidiana. ¿Sorprendidos?
Versión optimizada
Continuando con lo que nos importa, todos los lenguajes de programación tienen estructuras de información del tipo clave + valor (almacena una información concreta llamada valor asociada a una clave, por ejemplo, un entero o una cadena de texto) que se apoyan en los códigos hash para su funcionamiento y que hacen que la búsqueda de información en este tipo de estructuras sean extremadamente rápida y eficiente. Con esta premisa de partida vamos a presentar el algoritmo de antes reescrito con este enfoque:
public void showBooks(ArrayList<BookBean> books, ArrayList<UserBean> users)
{
HashMap<Integer, UserBean> hashUsers = new HashMap<Integer, UserBean>();
for (UserBean user : users)
{
hashUsers.put(user.getUserId(), user);
}
for (BookBean book : books)
{
UserBean userFound = hashUsers.get(book.getUserId());
System.out.println(book.getName() + " " + user.getName());
}
}
En este algoritmo vemos que de alguna manera hemos sacado el bucle interno de usuarios a un bucle previo al que se usa para recorrer los libros. Lo que hacemos realmente es recorrer primero los usuarios una única vez para meterlos en una estructura de tipo clave + valor que se apoya en códigos hash para su funcionamiento, en el caso de este ejemplo en java usamos HashMap. Después cuando recorremos los libros simplemente obtenemos el usuario asociado directamente del HashMap y listo.
Ahora en lugar de multiplicar el número de iteraciones de un bucle por el número de iteraciones del otro, las tenemos que sumar ya que ahora los bucles se recorren por separado. Podría parecer entonces que ahora el número de iteraciones es de 10.000 (libros) + 1.000 (usuarios), pero esto no es verdad, porque aunque no lo veamos en nuestro código, realmente la línea hashUsers.put(user.getUserId(), user) utiliza internamente bucles para obtener el usuario que buscamos, pero al apoyarse en códigos hash el número de bucles ejecutados en este caso de java, se puede aproximar como log2(n), en nuestro caso sería log2(1.000) que es aproximadamente 10, es decir nuestras 500 iteraciones medias internas de la versión anterior equivaldrían ahora a 10, lo que hace que el número total de iteraciones sea de:
10.000 (libros) x 10 (hash usuarios) + 1.000 (usuarios) = 101.000.
Si comparamos nuestras 5.000.000 de iteraciones iniciales con las 101.000 actuales, vemos que el algoritmo inicial tenía un consumo de 49.5 veces el consumo del algoritmo optimizado o, dicho de otra forma, el algoritmo optimizado sólo usa el 2,02% de los recursos que utilizaba el original. Suena bien, ¿no?
Para finalizar el artículo y ponerle datos reales a esta optimización he creado un poquito de código con los dos algoritmos indicados utilizando 10.000.000 libros y 1.000.000 usuarios con el objetivo de que salgan tiempos un poco grandes para poder compararlos y lo he lanzado numerosas veces. En el primer caso el tiempo de ejecución medio fue de unos 13 segundos y en el segundo caso de unos 300 milisegundos (0.3 segundos).
Como veis el ahorro de recursos es extremadamente alto y el algoritmo nuevo no es nada complicado de implementar con respecto al original, así que es bastante productivo aplicar el cambio de forma sistemática a partir de ahora cuando os encontréis este tipo de casos.
Hash codes and software optimization [EN]
Those of us who are dedicated to software programming know how important algorithm optimization is to reduce the resources necessary to execute a certain process. In this article we are going to analyze a very common case, in which applying a very simple technique with hash codes, amazing results are obtained.
Optimizing an algorithm provides us with two important benefits:
- Obtain the result of the process more quickly. An example of this could be reducing the response time of a web page that has to do a lot of calculations when a customer requests it.
- Be able to execute more simultaneous processes in a given time. An example of this could be increasing the number of web pages that a particular server can display and thus increasing the number of concurrent users supported by that server.
Optimizing a process is something quite manual since depending on the operations that are executed and the subprocesses that are launched, very different paths must be taken to reduce time. There are even cases in which the best optimization consists of rethinking the entire process and developing it in a completely different way, but there are techniques that are useful in many common cases and that should always be on hand to use systematically when programming. This is the case of using hash codes in repetitive processes and that is what we will discuss in this article.
Initial version
Let's consider a very common hypothetical case, nested loops. Suppose we have a list of users and that each of them can have books associated with them, for example, in library loans. Now suppose that someone asks us for a list of all the books, showing each one of them with the user that is associated with it. To solve this case, the following standard algorithm could be proposed (I will present it in Java language but logically it can be extrapolated to any programming language):
public void showBooks(ArrayList<BookBean> books, ArrayList<UserBean> users)
{
for (BookBean book : books)
{
UserBean userFound = null;
for (UserBean user : users)
{
if (book.getUserId() == user.getUserId())
{
userFound = user;
break;
}
}
System.out.println(book.getName() + " -> " + user.getName());
}
}
Initial version explanation
In this algorithm we see how two nested "for" loops are executed where in the first we go through the books that the library has and in the second, for each book, we go through the users until we find the user associated with the book. With this algorithm, if we have 10,000 books and 1,000 users, for example, the number of iterations would be:
10,000 (books) x 1,000 (users) = 10,000,000
It is true that the use of the break statement means that when we find a user of a book we no longer continue searching the rest of the users for that book, which means that it can be said that the number of iterations of the internal loop is approximately half, that is, we are applying a first optimization where the number of total iterations would be:
10,000 (books) x 500 (average users with break) = 5,000,000
Now the objective is to reduce that number of iterations and for this we can take advantage of hash codes, those same hash codes that you may have heard mentioned as one of the pillars that make our beloved blockchains work. A hash code can be understood as a "summary" of some information, and we all know that it is easier to search for something in a summary than in the complete information. In another article I will talk in more detail about hash codes, how they work and that, without being aware of it, our brains use this concept regularly in our daily lives. Surprised?
Optimized version
Continuing with what matters to us, all programming languages have information structures of the type key + value (stores specific information called value associated with a key, for example, an integer or a text string) that are supported by codes. hash for its operation and that make the search for information in this type of structures extremely fast and efficient. With this starting premise we are going to present the previously rewritten algorithm with this approach:
public void showBooks(ArrayList<BookBean> books, ArrayList<UserBean> users)
{
HashMap<Integer, UserBean> hashUsers = new HashMap<Integer, UserBean>();
for (UserBean user : users)
{
hashUsers.put(user.getUserId(), user);
}
for (BookBean book : books)
{
UserBean userFound = hashUsers.get(book.getUserId());
System.out.println(book.getName() + " " + user.getName());
}
}
In this algorithm we see that, somehow, we have removed the internal user loop to a loop prior to the one used to show the books. What we really do is first go through the users once to put them in a key + value type structure that relies on hash codes for its operation. In the case of this Java example we use HashMap. Then, when we go through the books and we get the associated user directly from the HashMap, and that's it.
Now, instead of multiplying the number of iterations of one loop by the number of iterations of the other, we have to add them since now the loops are run separately. It might seem then that now the number of iterations is 10,000 (books) + 1,000 (users), but this is not true, because although we do not see it in our code, actually the line hashUsers.put(user.getUserId(), user) internally uses loops to obtain the user we are looking for, but by relying on hash codes the number of loops executed in this Java case can be approximated as log2(n), in our case would be log2(1,000) which is approximately 10, that is, our 500 internal average iterations of the previous version would now be equivalent to 10, which makes the total number of iterations:
10,000 (books) x 10 (user hash) + 1,000 (users) = 101,000.
If we compare our initial 5,000,000 iterations with the current 101,000, we see that the initial algorithm had a consumption of 49.5 times the consumption of the optimized algorithm or, in other words, the optimized algorithm only uses 2.02% of the resources that used the original. Sounds good, right?
To finish the article and put real data to this optimization, I have created a little code with the two indicated algorithms using 10,000,000 books and 1,000,000 users with the aim of producing times that are a bit long to be able to compare them and I have launched it numerous times. In the first case the average execution time was about 13 seconds and in the second case about 300 milliseconds (0.3 seconds).
As you can see, the resource savings are extremely high and the new algorithm is not at all complicated to implement compared to the original, so it is quite productive to apply the change systematically from now on when you encounter these types of cases.