Un ejemplo para un amigo: El par de puntos más próximo

En este año he tenido la suerte de conocer a un grupo de personas fantásticas y con una de ellas, con pinta de "despistado" y con un corazón que no le cabe debajo de la corbata, tengo siempre debates sobre informáticos y programadores en las startups tecnológicas. En una de las últimas hablamos de la importancia de conocer o no determinados lenguajes de programación a la hora de elegirlos. 

El problema de base

Yo soy de los que cree que se debe saber C, POO en C++ o Java, algorítmica, estructuras de datos y ... un poco de ensamblador. El resto es accesorio, y basta con ponerse manos a la obra con el lenguaje y el compilador. Para explicar esto a mi amigo, voy a aprovecharme de este post y describir cómo solucionar un problema aparentemente sencillo:

En una nube de puntos descubrir qué par de ellos están más cerca entre si.

Esto de buscar el par de puntos más cerca en un espacio n-dimensional puede aplicarse a solucionar cualquier problema que tenga que ver con la búsqueda de similitudes, que puede ir desde descubrimiento de perfiles similares a la detección de copias o falsificaciones. Lo que representes en los ejes de las dimensiones es cosa tuya.

La solución de un mal programador

Para resolver este problema en un espacio de dos dimensiones con una nube de puntos desordenados sería bastante evidente el calcular todas las distancias entre todos los puntos y comparar luego todas las distancias entre sí para saber cuál es la menor.

Esta aproximación resuelve el problema, pero es una solución ineficiente que no debe ser implementada en ningún producto que vaya a escalar, ya que para n elementos, el tiempo de resolución tiende a 2 veces n elevado a 2. Es decir, para 100 elementos se necesitan unas 20.000 iteraciones - a grosso modo -. Es decir, n*n distancias + n*n comparaciones entre ellas para saber cuál es la más pequeña.

Una "cagada" de solución que se cargará cualquier proyecto tecnológico que tenga éxito y muchos elementos a comparar.

La solución de un arquitecto de software

Resolver este problema es algo que ya hace años que está pensado y estudiado, y la solución es mucho más elegante. Se basa en la aplicación de un algoritmo de recta de barrido. Vamos por partes.

Si tenemos los puntos ordenados por su coordenada X e inicializamos la distancia menor M a la distancia entre los dos puntos con menores coordenadas X no será necesario calcular la distancias entre un punto y aquellos que sus coordenadas X estén a una distancia mayor que la distancia M. Esto permite reducir el número de comparaciones a realizar, quedando reducido el problema de las distancias a k*n, donde k es el número medio de comparaciones que hay que hacer en cada punto. 

El árbol binario de búsqueda

Sin embargo, aplicar esto requiere de varios pasos previos. El primero de ellos es ordenar los puntos según se dan de alta, por lo que es necesario utilizar una estructura de datos que permita que la inserción de puntos en orden sea lo más eficiente, lo que nos lleva directamente a un árbol binario de búsqueda que deja que la inserción en orden sea un proceso logaritmo(n), pero... 

El árbol AVL

...esto puede llegar a ser ineficiente, si todos los puntos que se incorporan son introducidos siguiendo una progresión creciente o decreciente constante. Si se diera esa situación el árbol binario de búsqueda degeneraría en una lista y el tiempo medio del proceso de inserción ordenada dejaría de ser logarítmico para acabar a ser lineal, es decir, que para n elementos tomaría n/2 pasos. Para solucionar este problema, hace años que los arquitectos de software desarrollaron los árboles AVL, árboles que se recolocan en el momento en que un nodo del árbol binario tiene un desequilibrio entre las alturas de las ramas.

Figura 1: árbol binario desequilibrado convertido en un árbol AVL

Es decir, si la rama de números menores tiene una altura H1 y la rama de números mayores tiene una altura H2 que cumple que H1>H2+1, entonces se recolocan los nodos para que la diferencia entre las dos ramas solo sea como máximo de 1. Esto garantiza que el árbol jamás degenera en una lista y siempre se consigue tener la lista de elementos ordenados en un tiempo eficiente pero...

EL árbol hilvanado o enhebrado por la lista

Para resolver eficientemente el problema hay que resolver el problema de los puntos en dos fases. La primera de ellas es recorrer los puntos uno tras otro por el eje de coordenadas X de izquierda a derecha. Después, por cada punto se debe buscar la lista de puntos más a la derecha en la coordenada X cuya distancia en X sea menor que la distancia menor M hasta el momento. Esto implica recorrer los puntos en orden de X y un árbol binario de búsqueda es muy eficiente para búsqueda de elementos e inserción, pero no para encontrar el siguiente o el anterior, ya que implica un proceso logarítmico y no un paso constante.

Figura 2: Ejemplo de un árbol hilvanado

Para solucionarlo, el proceso de inserción debe hacerse añadiendo también en cada nodo un par de punteros al anterior, y el siguiente, haciendo que el árbol AVL esté hilvanado por una lista doblemente enlazada - apuntando al anterior y al siguiente - lo que es una de las formas más eficientes de recorrer un árbol. Esto permite que el algoritmo tenga una complejidad de n*(log(n)).  Pero....

El árbol B+

... ¿qué pasaría si el número de puntos ocuparan mucho en memoria porque fueran estructuras pesadas o porque el número de ellos fuera tan grande que hubiera que pensar en almacenamiento en disco? Pues que habría que pensar en una estructura en disco que optimizase el número de lecturas que hubiera que realizar. Para ello se debe hacer un estudio del tamaño de sectores que es capaz de leer de una vez un cabezal de disco y meter más de un elemento junto, utilizando los árboles B+. En ellos hay varios elementos juntos formando una lista en cada nodo, y entre ellos forman una árbol.

Figura 3: Ejemplo de un árbol B+

Además, para que no haya que equilibrarlos como en los árboles binarios de búsqueda, los árboles B+ nacen de las hojas hacia arriba y evitan modificaciones masivas en las recolocaciones cuando el árbol estuviera desequilibrado.

Y aún más soluciones para el mismo problema

Como siempre, ésta no es la única solución posible para este problema, y haciendo uso de los Diagramas de Voronoi también es factible implementar una solución óptima [os dejo un manual sobre Geometría Computacional de Francisco Rivero para los más curiosos] para este problema, lo que permite ajustar aún más la solución dependiendo de los requisitos de implementación lo y casos concretos.

Figura 4: Diagrama de Voronoi

Así que, cuando hago las entrevistas a los programadores que van a recibir las becas Talentum Startups Long Track, les acabo preguntando cosas de estas sobre cómo es el funcionamiento de los algoritmos A*, los árboles AVL, o cómo funciona un Merge-Sort. Manías mías...

Saludos Malignos!