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!
¡Pero qué has hecho, inconsciente?
ResponderEliminarAhora, cuando preguntes cómo se abre un fichero de texto te dirán que se coge el fichero y se inserta en un árbol B que hay que transformar en un ADT polimórfico mediante una operación de transofrmada gaussiana con toques rococó y que luego se pasa por las coordenadas X esas.
Ya no podrás distinguir entre los que saben y los que no.
:-)
En parte no estoy de acuerdo con lo que has puesto. Y digo en parte porque por supuesto que esta claro que la segunda solución es mucho mejor(por complejidad del algoritmo y todas esas cosas), pero creo que el Arquitecto Software se dedica a un nivel más alto que eso, es decir, a pensar en la arquitectura y el diseño del programa, y no en los detalles de la implementación.
ResponderEliminarEs decir, si por ejemplo estuviésemos en un POO con clases(como Java o C++), el Arquitecto o Diseñador Software se encargaría de asignar la responsabilidad de resolver ese algoritmo a una cierta clase, definir su interfaz, usar patrones de diseño, una arquitectura software correcta, etc...Pero lo que hubiese dentro de esa clase sería más bien parte del programador, que en una primera pasada podría perfectamente dar la primera implementación para ir desarrollando el programa, y en una segunda pasada cambiar la implementación a la segunda, que es mucho más eficiente, sin tener que cambiar nada del programa ya que la interfaz de la clase seguiría siendo la misma.
En resumen, que creo que es más un problema de programación(osea, de implementación), que no de arquitectura/diseño, no se si se me entiende.
Un saludo.
En un mundo ideal, este estúpido detalle tendría su importancia, pero en el mundo real a nadie le importan los árboles B, ni cómo se implementan las claves en una BD, ni el algoritmo del glotón ni el problema de los sabios y los tenedores, ni lo que es un semáforo ni un monitor...
ResponderEliminarYa ves, tristemente he llegado a la conclusión que si a mi me importan es por solidaridad. Solidaridad con el pobre pardillo que tenga que tocar lo que yo he hecho, porque te puedo asegurar que lo puedes hacer todo con complejidad exponencial y espera activa y nadie se enterará... sólo el pobre que tenga que reformar algo, comprobado.
Sí, a veces me gusta hacer putadas ;)
Con qué le importe a una persona..ya basta y tiene de sobra..pero olé ahí esa humildad:))
EliminarSuena a que sabrías hacer un sistema de reconocimiento facial (cosa que me hará falta en el futuro, reconocimiento, no solo detección) y precisamente el problema que le veía al tema es que iban a ser millones y millones de fotos a comparar...
ResponderEliminarpero vamos que complicarse así ara algo casero lo veo innecesario...
Hay una errata. Donde dice "el tiempo de resolución tiende a 2 veces n elevado a n" debería decir "el tiempo de resolución tiende a 2 veces n elevado a 2".
ResponderEliminar@iñaki, gracias! }:))
ResponderEliminarPregunta, tengo dos cajones, de uno puedo sacar/meter 150 objetos por hora, del otro 90, meto 2000 objetos re partidos en 24 horas y saco otros 2000 en 8 que se 16 horas antes. Puedo repartir los objetos por los cajones para sacar 240 objetos a la . Hay algún genio que tenga ya un algoritmo para calcular esto??
ResponderEliminarPara calcular que? Solo has dicho lo que tienes, 2 cajones
ResponderEliminar/ts~
Perdón, me explico mejor.
ResponderEliminarTengo un conjunto de cargas de objetos definidas, se los objetos que debo cargar pero no se cuando exactamente, tengo 8 horas para hacerlo.
Puede ser en cualquier momento y además en paralelo hasta un máximo de 12 cargas simultaneas.
Los objetos los puedo sacar desde dos cajones, del primero puedo sacar 150 por hora y del segundo 90 por hora.
Los cajones los puedo llenar como quiera.
? cual es la forma mas eficiente de hacer el vaciado?
@Wolvbcn, deberías hacerte tú tus prácticas, que no hay que ser un genio para resolverlas... };)
ResponderEliminarSaludos!
Wolfbcn asi que no eres un bot e(hablo de foro.elhacker.net)
ResponderEliminarAunque el post sea antiguo, creo que vale la pena dejar este link http://bl.ocks.org/4060366
ResponderEliminarEs una applet que muestra un mapa de Voronoi interactivo
También hay una errata en el último algoritmo que comentas. No es merge-short, sino merge-sort
ResponderEliminarMuy bueno el post!
En teoría de códigos a esto le llamamos distancia mínima y está relacionado con el numero de errores que puedes detectar/corregir :)
ResponderEliminarRespeto a los lenguajes, hay que conocer Haskell y todo lo demás viene de gratis
No seria el algoritmo de Dijkstra la solucion optima del problema?
ResponderEliminarhttps://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra
@David, a este problema existen varias soluciones. Las explicadas aquí son dos de ellas. Dijkstra está diseñado para descubrir el camino más corto entre dos puntos calculando la suma de los pesos que lleva ir de uno a otro. Aunque se podría llegar a utilizar, las soluciones de la recta de barrido y de Voronoi resuelven este problema eficientemente.
ResponderEliminarSaludos!