Implementing randomized quad trees

Universitat Polit` ecnica de Catalunya Facultat d’Inform` atica de Barcelona Grau en Enginyeria Inform` atica - Computaci´ o Randomized Quad Trees: Implementation and Experimental Analysis Autor: Oliver Mart´ınez Pons Directora: Amalia Duch Brown 3 de Julio de 2019 Resumen Los quad trees propuestos por Bentley en el 1974 [7] son una estructura de datos dise˜nada para resolver b´usquedas asociativas [8]. Esta estructura es una generalizaci´on de los ´arboles binarios de b´usqueda y es interesante porque es cl´asica y es utilizada. Adem´as, es una estructura de datos jer´arquica de prop´osito general que puede ser generalizada f´acilmente a m´ultiples dimensiones [14]. El problema de los quad trees es que es dif´ıcil borrar elementos [13] o, dicho de otra manera, que sean din´amicos. Pese a que el borrado en dos dimensiones est´a definido por H. Samet [13], el algoritmo es complicado y dif´ıcil de implementar. Es m´as, este algoritmo tambi´en es dif´ıcil de generalizar para dimensiones mayores a 2. Adem´as, en el algoritmo cl´asico de inserci´on, la forma del ´arbol depende del orden en el que se insertan las llaves. Si las llaves son generadas de manera independiente por una distribuci´on de probabilidad continua, se obtiene un ´arbol aleatorio [5] cuya altura esperada es logar´ıtmica con respecto al n´umero de llaves del ´arbol, sin embargo, si las llaves se insertan en orden, la altura del ´arbol es lineal, lo que tiene un impacto en la eficiencia de las b´usquedas exactas en dicho ´arbol (que en el caso peor son de coste proporcional a la altura del ´arbol) y tambi´en en el de las b´usquedas asociativas. En el art´ıculo, Randomized insertion and deletion in point quad trees [4], se propone, utilizando algoritmos aleatorios [10], un algoritmo de borrado simple y escalable a m´as dimensiones. El algoritmo es f´acil de describir y de generalizar y es bastante m´as sencillo de implementar que el de Samet. Adem´as, los algoritmos de inserci´on y borrado en randomized quad trees garantizan que los quad trees resultantes sean siempre aleatorios. En este trabajo final de grado se estudian los algoritmos randomizados propuestos en el art´ıculo citado anteriormente, se implementan y se propone una implementaci´on alternativa y m´as eficiente que la original. Finalmente, se analiza experimental y exhaustivamente la eficiencia de los algoritmos de inserci´on y borrado propuestos. Posteriormente se comparan los resultados con algoritmos alternativos; una implementaci´on con cola de prioridad y una implementaci´on sin randomizar. Los resultados experimentales muestran que los algoritmos randomizados propuestos: 1) funcionan correctamente para cualquier dimensi´on (de hecho se han probado hasta dimensi´on 6, pero los al- 1 goritmos son v´alidos para cualquier dimensi´on, especialmente el borrado), 2) producen ´arboles aleatorios que cumplen con los costes esperados dados en la literatura [4], 3) compiten en eficiencia con la implementaci´on con cola de prioridad propuesta especialmente para dimensiones menores de 5, y 4) compiten en eficiencia (son mucho mejores) que el algoritmo de inserci´on cl´asico en el caso en el que las llaves a insertar no sean aleatorias o est´en dadas en orden. De hecho, este ´ultimo algoritmo no produce ´arboles aleatorios cuando las llaves no son generadas de manera aleatoria [3, 2]. 2 Resum Els quad trees proposats per Bentley en el 1974 [7] s´on una estructura de dades dissenyada per resoldre cerques associatives [8]. Aquesta estructura ´es una generalitzaci´o dels arbres binaris de cerca i s´on interessants perqu`e ´es cl`assica i ´es emprada. A m´es a m´es, ´es una estructura de dades jer`arquica de prop`osit general que pot ser generalitzada f`acilment per a m´ultiples dimensions [14]. El problema dels quad trees ´es que ´es dif´ıcil esborrar elements [13] o, dit d’altra manera, que siguin din`amics. Malgrat que l’esborrat en dues dimensions est`a ben definit per H. Samet [13], l’algoritme ´es complicat i dif´ıcil d’implementar. ´ Es m´es, aquest algoritme tamb´e ´es dif´ıcil de generalitzar per a dimensions majors a 2. A m´es a m´es, en l’algoritme cl`assic d’inserci´o, la forma de l’arbre dep`en de l’ordre en qu`e s’insereixen les claus. Si les claus s´on generades de manera independent per una distribuci´o de probabilitat cont´ınua, s’obt´e un arbre aleatori [5] el qual l’altura esperada ´es logar´ıtmica respecte el nombre de claus del arbre, tanmateix, si les claus s’insereixen en ordre, l’altura de l’arbre ´es lineal, cosa que t´e un impacte en l’efici`encia de les cerques exactes en aquest arbre (que en el pitjor cas s´on de cost proporcional a l’altura de l’arbre) i tamb´e en el de les cerques associatives. En l’article, Randomized insertion and deletion in point quad trees [4], es proposa, emprant algoritmes aleatoris [10], un algoritme de esborrat simple i escalable a m´es dimensions. L’algoritme ´es f`acil de descriure i de generalitzar i ´es bastant m´es senzill d’implementar que el de Samet. A m´es a m´es, els algoritmes d’inserci´o i esborrat en randomized quad trees garanteixen que els quad trees resultants siguin sempre aleatoris. En aquest treball final de grau s’estudien els algoritmes randomizats proposats en l’article citat anteriorment, s’implementen i es proposa una implementaci´o alternativa i m´es eficient que l’original. Finalment, s’analitza experimental i exhaustivament l’efici`encia dels algoritmes d’inserci´o i esborrat proposats. Posteriorment es comparen els resultats amb algoritmes alternatius; una implementaci´o amb cua de prioritat i una implementaci´o sense randomitzar. Els resultats experimentals mostren que els algoritmes randomizats proposats: 1) funcionen correctament per a qualsevol dimensi´o (de fet s’han provat fins a dimensi´o 6, per`o els algoritmes s´on v`alids per a qualsevol dimensi´o, especialment el esborrat), 2) produeixen arbres 3 aleatoris que compleixen amb els costos esperats donats en la literatura [4], 3) competeixen en efici`encia amb la implementaci´o amb cua de prioritat proposta especialment per a dimensions menors que 5, i 4) competeixen en efici`encia (s´on molt millors) que l’algoritme d’inserci´o cl`assic en el cas en qu`e les claus a insertar no siguin aleat`ories o est´en donades en ordre. De fet, aquest ´ultim algoritme no produeix arbres aleatoris quan les claus no s´on generades de manera aleat`oria [3, 2]. 4 Abstract The quad trees proposed by Bentley in 1974 [7] are a data structure designed to solve associative queries [8]. This structure is a generalization of binary search trees and is interesting because it is classical and it is used. In addition, it is a general-purpose hierarchical data structure that can easily be generalized to multiple dimensions [14]. The problem with quad trees is that it is difficult to delete elements [13], or in other words, to be dynamic. Although the twodimensional deletion is defined by H. Samet [13], the algorithm is complicated and difficult to implement. Moreover, this algorithm is also difficult to generalize for dimensions greater than 2. In addition, in the classic algorithm of insertion, the shape of the tree depends on the order in which the keys are inserted, if the keys are generated independently by a continuous probability distribution, a random tree is obtained [5], whose expected height is logarithmic in regard to the number of keys of the tree, however, if the keys are inserted in order, the height of the tree is linear, which has an impact on the efficiency of the exact searches in said tree ( which in worst case their cost is proportional to the height of the tree) and also in the associative queries. In the article, Randomized insertion and deletion in point quad trees [4], it is proposed, using random algorithms [10], a simple and scalable deletion algorithm for more dimensions. The algorithm is easy to describe and generalize and is much simpler to implement than the Samet algorithm. In addition, the insertion and deletion algorithms in randomized quad trees guarantee that the resulting quad trees are always random. In this final degree project, the randomized algorithms proposed in the aforementioned article are studied and implemented, and an alternative and more efficient implementation than the original one is proposed. Finally, the efficiency of the proposed insertion and deletion algorithms is experimentally and exhaustively analysed. Subsequently, the results are compared with alternative algorithms; an implementation with priority queue and an implementation without randomization. The experimental results show that the proposed randomized algorithms: 1) work correctly for any dimension (in fact they have been tested up to dimension 6, but the algorithms are valid for any dimension, especially the deletion), 2) produce random trees that meet 5 the costs expected in the literature [4], 3) compete in efficiency with the implementation with priority queue proposed especially for dimensions less than 5, and 4) compete in efficiency (are much better) than the classical insertion algorithm in the case where the keys to be inserted are not random or are given in order. In fact, this last algorithm does not produce random trees when the keys are not generated randomly [3, 2]. 6 Contenidos 1 Introducci´on 9 2 Preliminares 11 2.1 B´usquedas asociativas . . . . . . . . . . . . . . . . . . . . . . 11 2.2 Definici´on de Quad trees . . . . . . . . . . . . . . . . . . . . . 12 3 Randomized Quad trees 17 3.1 Definici´on ............................. 17 3.2 Implementaci´on original . . . . . . . . . . . . . . . . . . . . . 18 4 Algoritmos e Implementaci´on 20 5 Experimentaci´on y an´alisis experimental 25 5.1 Costes de los algoritmos . . . . . . . . . . . . . . . . . . . . . 25 5.1.1 Coste de creaci´on . . . . . . . . . . . . . . . . . . . . . 26 5.1.2 Coste de insertado . . . . . . . . . . . . . . . . . . . . 28 5.1.3 Coste de borrado . . . . . . . . . . . . . . . . . . . . . 30 5.1.4 Coste de la inserci´on en la ra´ız . . . . . . . . . . . . . . 32 5.1.5 Coste del borrado en la ra´ız . . . . . . . . . . . . . . . 34 5.1.6 An´alisis de los costes . . . . . . . . . . . . . . . . . . . 36 5.2 Comparativas ........................... 37 5.2.1 Coste de creaci´on . . . . . . . . . . . . . . . . . . . . . 38 7 5.2.2 Coste de inserci´on . . . . . . . . . . . . . . . . . . . . . 41 5.2.3 Coste de borrado . . . . . . . . . . . . . . . . . . . . . 43 6 Planificaci´on y an´alisis econ´omico 46 6.1 Planificaci´on............................ 46 6.2 An´alisis econ´omico . . . . . . . . . . . . . . . . . . . . . . . . 48 7 Sostenibilidad 50 7.1 Dimensi´on ambiental . . . . . . . . . . . . . . . . . . . . . . . 50 7.2 Dimensi´on econ´omica . . . . . . . . . . . . . . . . . . . . . . . 50 7.3 Dimensi´on social . . . . . . . . . . . . . . . . . . . . . . . . . 51 8 Conclusiones y trabajo futuro 52 8.1 Conclusiones............................ 52 8.2 Trabajofuturo .......................... 53 8 Figura 3: Inserci´on de un nodo 5 en el quad tree. Ahora vamos a borrar la llave 4. El algoritmo la busca y la elimina. Ahora tenemos que hacer algo con 5. Como hemos descrito anteriormente, el algoritmo cl´asico reinsertara el nodo 5desde la ra´ız siguiendo el algoritmo de insertado quedando de la siguiente manera: Figura 4: Quad tree tras borrar el nodo 4. Los quad trees pueden ser generalizados f´acilmente a m´ultiples dimensiones [14]. Un quad tree k-dimensional consiste pues, en un ´arbol k-ario donde cada nodo guarda una tupla de kvalores y tiene 2ksub´arboles [7]. Por tanto, cada llave del ´arbol dividir´a el espacio de b´usqueda en 2khiper- cuadrantes donde cada uno de ellos corresponder´a a una permutaci´on de comparaciones donde cada atributo es mayor o menor que el del nodo padre. 15 Y la definici´on formal es la siguiente: Definici´on 2 Un quad tree Tde tama˜no n≥0es una colecci´on de nregistros k-dimensionales, que consisten en una llave x= (x0, . . . , xk−1)∈ D, donde D=D0× · · · × Dk−1, y cada Dj,0≤j < k, es un dominio completamente ordenado. El quad tree Tes un ´arbol 2k-ario tal que •o bien es vac´ıo y n= 0, o •su ra´ız guarda una llave xy tiene 2ksub´arboles, cada uno asociado a una secuencia de bits de longitud k w =w0w1. . . wk−1∈ {0,1}k, y las dem´as n−1llaves restantes est´an guardadas en uno de sus sub´arboles Tw, tal que ∀w∈ {0,1}k:Twes un quad tree y para cada llave y∈Tw, se cumple que yj< xjsi wj= 0 yyj> xjsi wj= 1 ,0≤j < k. El problema de los quad trees es que el algoritmo de borrado es muy costoso [13] y destruye la aleatoriedad del ´arbol en caso de que este lo fuese. Como ya mencionamos anteriormente, existe un borrado eficiente en dos dimensiones definido por H. Samet [13] pero el algoritmo es complicado y dif´ıcil de implementar. Es m´as, este algoritmo tambi´en es dif´ıcil de generalizar para dimensiones mayores que 2 y es tan complicado que la soluci´on que se ha adoptado en la pr´actica es la de reconstruir el sub´arbol completo afectado por un borrado, lo que claramente incurre en costes m´as altos de los algoritmos. Otro problema del borrado es que, si tenemos un ´arbol generado con nodos aleatorios, tras cada borrado el ´arbol se desbalancea y pierde eficiencia. Es m´as, si las llaves que se insertan no son generadas aleatoriamente (por ejemplo, est´an ordenadas creciente o decrecientemente) el ´arbol no es aleatorio y no se cumplen los costes logar´ıtmicos. Para resolver estos problemas podemos hacer uso de los Randomized quad trees que explicamos en la siguiente secci´on. Antes de continuar damos la definici´on formal de random quad tree que es la siguiente: Definici´on 3 Un random quad tree de tama˜no nes un quad tree construido insertando nllaves independientes escogidas de una distribuci´on de probabilidad continua definida sobre [0,1]k. 16 3 Randomized Quad trees 3.1 Definici´on Los randomized quad trees se diferencian de los quad trees originales porque ahora los nodos adem´as de contener una tupla de katributos, donde kes la dimensi´on del ´arbol, estos contienen un atributo extra al que llamaremos prioridad [16]. Definici´on 4 Un quad tree es un randomized quad tree si para cada nodo, los hijos de este o bien son nulos o su prioridad es inferior a la del padre. En particular cabe observar que si las prioridades se generan de manera independiente y uniformemente a partir del intervalo [0,1], un randomized quad tree es un random quad tree y por tanto se cumplen todas las propiedades te´oricas demostradas para los random quad trees [9, 16, 10, 4]. En la Figura 5 se puede ver un quad tree con prioridades que no cumple esta condici´on y por tanto no es un randomized quad tree mientras que el ´arbol a su derecha s´ı que lo es. Figura 5: Quad tree no randomized a la izquierda y randomized a la derecha. Esta propiedad que hace que los ´arboles sean randomized nos permite crear 17 ´arboles que no se vean afectados por el orden de los nodos insertados siempre y cuando los algoritmos de inserci´on y borrado nos produzcan randomized quad trees como resultado [4]. 3.2 Implementaci´on original A continuaci´on, vamos a ver c´omo funcionan los algoritmos de inserci´on y borrado basados en Randomized insertion and deletion in point quad trees [4]. Como hemos comentado, los nodos ahora adem´as de ser una tupla de katributos, donde kes la dimensi´on del ´arbol, este contiene un atributo extra al que llamaremos prioridad y ser´a un n´umero generado uniformemente en el intervalo [0,1] y de manera independiente para cada llave. Lo que queremos con esto es que el insertado y borrado produzcan ´arboles que se comporten como si hubiesen sido creados por llaves generadas uniforme e independientemente. Para ello queremos que el insertado tenga una cierta probabilidad de convertir al nuevo nodo en la ra´ız del ´arbol. De la misma manera, cuando un nodo es borrado es necesario que los nodos inferiores tengan una probabilidad de remplazarlo. Siendo Tun ´arbol y xun nodo a insertar, el algoritmo de inserci´on proceder´a de la siguiente manera: 1. Si el ´arbol Test´a vac´ıo, el algoritmo crea un ´arbol con ra´ız xy 2k sub´arboles vac´ıos. 2. Si el ´arbol Tno est´a vac´ıo y la prioridad de xes mayor que la prioridad de la ra´ız de T, entonces xse convertir´a en la nueva ra´ız del ´arbol y sus sub´arboles ser´an el resultado de llamar a la funci´on split sobre T. Si la prioridad no es mayor entonces xser´a insertada recursivamente en el sub´arbol de Tque le corresponda por sus atributos. Por otra parte, el algoritmo de borrado buscar´a el nodo a borrar y una vez encontrado llamar´a a la funci´on join para juntar sus 2ksub´arboles para remplazarlo como nuevo ´arbol. 18 Ahora vamos a explicar los algoritmos de split yjoin que utilizan los algoritmos de inserci´on y borrado. Dada una llave xy un ´arbol Tel algoritmo split devuelve un nuevo ´arbol T0con ra´ız x0y con los 2ksub´arboles correspondientes. Es decir, para cada nodo de T, este habr´a sido reasignado al sub´arbol correspondiente del nuevo ´arbol T0con ra´ız x0. Por su parte el algoritmo join recibe un conjunto de 2k´arboles Cy devuelve un nuevo ´arbol cuya ra´ız es la ra´ız con m´as prioridad de entre los 2k ´arboles de C. Los algoritmos de split yjoin se llaman el uno al otro para ir construyendo el ´arbol. El split parte el ´arbol respecto a la nueva ra´ız y el join junta los sub´arboles en uno solo y vuelve a llamar al split con la nueva ra´ız. Esta propuesta fue implementada pero su coste era muy elevado y no pod´ıa competir con los dem´as algoritmos dado que los algoritmos de split yjoin recorr´ıan el quad tree completo m´ultiples veces. Por ello, inspir´andonos en los algoritmos propuestos, se implement´o una propuesta que aprovechaba las ideas de los algoritmos de split yjoin y que pod´ıa competir con los dem´as algoritmos. Aun as´ı, la nueva implementaci´on podr´ıa ser mejorada a´un m´as dado que ciertas propiedades de la implementaci´on original que permit´ıan ahorrar visitas a nodos no han sido incluidas a´un. 19 4 Algoritmos e Implementaci´on En esta secci´on explicamos los algoritmos de inserci´on y de borrado que proponemos para los randomized quad trees. Estos funcionan igual que en la propuesta anterior. Eso s´ı, los algoritmos de inserci´on y de borrado utilizan a su vez otros dos algoritmos que aun llamarse de el mismo modo que los algoritmos originales hacen cosas distintas: el algoritmo split y el algoritmo join. Comenzaremos presentando el algoritmo split cuyo c´odigo se encuentra en el Programa 2. El objetivo de este algoritmo es agrupar todos los nodos de un ´arbol dado seg´un su relaci´on de orden con una llave dada. Por tanto, este algoritmo recibe como entradas un quad tree k-dimensional Ty una llave x. En una primera etapa, este algoritmo produce una matriz de 2kfilas tal que cada fila ide la matriz contiene los elementos del ´arbol que ir´ıan en el sub´arbol i-´esimo de un nuevo randomized quad tree k-dimensional que tuviese ra´ız x. En la segunda etapa para cada fila de la matriz llama al algoritmo join que devuelve un randomized quad tree formado por los elementos contenidos en dicha fila. Finalmente, el algoritmo split devuelve un vector de randomized quad trees que contiene en cada posici´on iun puntero al i-´esimo sub´arbol del randomized quad tree con ra´ız xque contiene todas las llaves del ´arbol original T. Cabe mencionar que el algoritmo split recorre el ´arbol Tpor niveles (utilizando el algoritmo cl´asico de recorrido en anchura de un grafo [1]). Por su parte, el algoritmo join (mirar Programa 3) como ya se ha dicho, recibe como par´ametro un vector de llaves y produce un randomized quad tree con esas llaves (respectando las prioridades correspondientes). Para ello, La funci´on join buscara cu´al de los nodos recibidos tiene m´as prioridad para convertirlo en la ra´ız del nuevo sub´arbol. 20 Una vez seleccionado, los nodos ser´an vueltos a separar en una matriz como hace el algoritmo split pero ahora respecto al nodo que ha sido elegido como ra´ız del sub´arbol. Por ´ultimo, la funci´on es llamada recursivamente para cada fila de la matriz una vez que los nodos han sido reasignados respecto a la nueva ra´ız. Vamos a verlo con un ejemplo. Imaginemos que tenemos el quad tree bidimensional Tde la Figura 6 y queremos insertar el nodo xcon prioridad 9. Figura 6: A la izquierda el quad tree original y a la derecha tras superponer el nodo 9 que se va a insertar. Como el nodo tiene m´as prioridad que la ra´ız actual del ´arbol, se llamar´a a la funci´on split que partir´a el ´arbol en 4 cuadrantes respecto a 9. Ahora se llamar´a a la funci´on join en cada nuevo cuadrante. Esta seleccionar´a el nodo con m´as prioridad y lo har´a ra´ız del nuevo sub´arbol. Ahora los nodos restantes ser´an vueltos a repartir respecto a la nueva ra´ız y ser´an juntados recursivamente mediante el algoritmo join. 21 Figura 7: A la izquierda el resultado de el algoritmo split donde el nodo con prioridad 9 es la ra´ız y los dem´as nodos est´an agrupados por cuadrantes. A la derecha la ejecuci´on del primer join en cada cuadrante. Figura 8: El resultado final tras ejecutar el algoritmo join recursivamente. Antes de ver los c´odigos, es conveniente presentar el struct QuadtreeNode con el que operan los algoritmos. Cada nodo del quad tree consiste en una instancia de este struct que a su vez consiste en una llave xque contiene los k atributos seguido de la prioridad y un vector de 2kpunteros a los sub´arboles, que tambi´en consisten en instancias del struct QuadtreeNode. 22 Programa 1 Implementaci´on en C++ de la estructura QuadtreeNode typedef vector<double > Key ; struct QuadtreeNode { Key x; vector < QuadtreeNode *> child ; QuadtreeNode(const Key & _x ) : x(_x ), child ( int(exp2 (K)), NULL ) {} }; Por otra parte, tenemos la funci´on subtree to insert que, dados dos nodos, nos devuelve un ´ındice ique indica el i-´esimo sub´arbol en el que el primer nodo deber´ıa ser insertado respecto al segundo. Programa 2 Implementaci´on en C++ del algoritmo split // INPUT : una llave x y un arbol T // OUTPUT : 2^k subarboles de x con los nodos de T vector < QuadtreeNode *> split ( const Key& x, QuadtreeNode *& T){ vector < QuadtreeNode *> childs ( int( exp2 (K)) , NULL ); if(not T) return childs; vector <vector < QuadtreeNode *> > matrix (int(exp2(K))); queue < QuadtreeNode *> q; q.push (T); // busqueda en anchura donde separamos todos los nodos de T // respecto a x en la matriz creada while (not q. empty ()){ QuadtreeNode * act = q. front (); q. pop (); auto w= subtree_to_insert (act ->x ,x); matrix [w ]. push_back ( new QuadtreeNode (act ->x )); for(int j = 0; j <int(exp2 (K)); ++j){ if( act -> child [j ]){ q. push (act -> child [j ]); } } } // llamadas a join para cada fila de la matriz que nos devolvera // el subarbol resultante para esa fila for(int j = 0; j <int( exp2 (K)); ++j) childs [j] = join ( matrix [j ]); return childs; } 23 Programa 3 Implementaci´on en C++ del algoritmo join // INPUT : un vector de llaves // OUTPUT : un arbol randomizado construido a partir de las llaves QuadtreeNode * join (vector < QuadtreeNode * >& child ){ double max= -1; int imax= -1; // Busca la llave con prioridad maxima del vector de entrada for(int i = 0; i < child .size (); ++i){ if( child [i] and ( child [i]->x )[ K] > max ){ max= child [i]->x[K] ; imax = i; } } if( imax == -1 ) return NULL; else{ // la llave con prioridad maxima se convierte en la raiz QuadtreeNode * T = child [imax ]; vector <vector < QuadtreeNode *> > matrix (int(exp2(K))); // separamos las llaves respecto a la nueva raiz // como haciamos en el algoritmo split for(int i = 0; i <int( child . size ()); ++ i) if(i!= imax ){ int w= subtree_to_insert ( child [i]->x , child [ imax ]->x ); matrix [w]. push_back ( child [i ]); } // llamamos recursivamente a join para obtener los subarboles // de la nueva raiz for(int j = 0; j< int( exp2 (K)); ++j){ T-> child [j] = join ( matrix [j ]); } return T; } } 24 Figura 15: Coste medio de borrado en nodos visitados para quad trees de dimensiones k=2,3,4,5,6 y tama˜no nde 25000 a 50000 Figura 16: Tiempo medio de borrado en nodos visitados para quad trees de dimensiones k=2,3,4,5,6 y tama˜no nde 25000 a 50000 Como podemos ver el coste sigue siendo mayor para dimensiones m´as peque˜nas y el tiempo sigue siendo m´as r´apido en dimensi´on 3. 31 Figura 17: Coste medio de borrado en nodos visitados para quad trees de dimensiones k=2,3,4,5,6 y tama˜no nde 25000 a 50000 dividido por log(n) log(log(n)) El coste de borrado parece ser del orden Θ(log(n) log(log(n))) tras dividir los resultados. Esto coincidir´ıa con los experimentos anteriores ya que el coste de borrado es igual que el coste de inserci´on al usar los mismos algoritmos. 5.1.4 Coste de la inserci´on en la ra´ız Ahora veremos el coste de inserci´on promedio en nodos visitados cuando el nodo insertado tiene m´as prioridad que la ra´ız del ´arbol en la Figura 18 y el tiempo de inserci´on promedio en la Figura 19. 32 Figura 18: Coste medio de inserci´on en la ra´ız en nodos visitados para quad trees de dimensiones k=2,3,4,5,6 y tama˜no nde 25000 a 50000 Figura 19: Tiempo medio de inserci´on en la ra´ız en nodos visitados para quad trees de dimensiones k=2,3,4,5,6 y tama˜no nde 25000 a 50000 En este experimento podemos comprobar que ahora s´ı el algoritmo m´as r´apido es el de dos dimensiones pese a visitar m´as nodos. 33 Figura 20: Coste medio de inserci´on en la ra´ız en nodos visitados para quad trees de dimensiones k=2,3,4,5,6 y tama˜no nde 25000 a 50000 dividido por nlog(n) El coste de inserci´on parece ser del orden Θ(nlog(n)) tras dividir los resultados. Esto confirmar´ıa los costes conseguidos en los experimentos anteriores, explicaremos c´omo posteriormente. 5.1.5 Coste del borrado en la ra´ız Ahora veremos el coste de borrado promedio en nodos visitados cuando el nodo insertado tiene m´as prioridad que la ra´ız del ´arbol en la Figura 21 y el tiempo de inserci´on promedio en la Figura 22. 34 Figura 21: Coste medio de borrado en la ra´ız en nodos visitados para quad trees de dimensiones k=2,3,4,5,6 y tama˜no nde 25000 a 50000 Figura 22: Tiempo medio de borrado en la ra´ız en nodos visitados para quad trees de dimensiones k=2,3,4,5,6 y tama˜no nde 25000 a 50000 Podemos ver que el coste de borrado es muy similar al de inserci´on. 35 Figura 23: Coste medio de borrado en la ra´ız en nodos visitados para quad trees de dimensiones k=2,3,4,5,6 y tama˜no nde 25000 a 50000 dividido por nlog(n) El coste de borrado parece ser del mismo orden que la inserci´on, Θ(nlog(n)). 5.1.6 An´alisis de los costes Como hemos visto en los experimentos, los costes de inserci´on y borrado promedios serian del orden Θ(log(n) log(log(n))), la creaci´on Θ(nlog(n) log(log(n))) y la inserci´on y el borrado en la ra´ız Θ(nlog(n)). El coste de creaci´on concuerda con el de inserci´on dado que la creaci´on consiste en una sucesi´on de ninserciones. Este a su vez concuerda con el coste de borrado ya que utiliza los mismos algoritmos que la inserci´on. Por ´ultimo, el coste de inserci´on y borrado en la ra´ız tambi´en concuerda con el coste de inserci´on y borrado promedio ya que como el tama˜no promedio de un sub´arbol elegido al azar de un ´arbol de tama˜no nes del orden de Θ(log(n)) [9], al substituir npor log(n) en el coste de inserci´on en la ra´ız, nlog(n), nos queda Θ(log(n) log(log(n))) que es el coste promedio de inserci´on y borrado promedio que hemos obtenido. 36 Cabe destacar que intuitivamente creemos que la funci´on que describe el coste promedio (medido como el n´umero de nodos visitados) de los algoritmos randomizados de inserci´on y de borrado es del orden Θ(log(n) + log(n) log(log(n))) para un quad tree de tama˜no n. Esto es debido a que ambos algoritmos constan de dos etapas: •La primera etapa consiste en localizar el sitio del ´arbol en donde se va a realizar la inserci´on o el borrado (esto corresponde a recorrer un camino del ´arbol con coste promedio Θ(log(n)) donde nes el tama˜no del ´arbol). •La segunda etapa consiste en aplicar en ese punto el algoritmo de split ojoin en sub´arboles de tama˜no promedio Θ(log(n)) [9]. La combinaci´on de los costes de ambas etapas explica el coste propuesto que adem´as parece verificarse experimentalmente. 5.2 Comparativas Ahora compararemos nuestra implementaci´on con la implementaci´on con cola de prioridad y la no randomizada. En la implementaci´on con cola de prioridad los nodos siguen teniendo prioridades, pero a la hora de insertar un nodo en la ra´ız, los sub´arboles son pasados a una cola de prioridad e insertados en orden de prioridad nuevamente utilizando el algoritmo de inserci´on. En la implementaci´on no randomizada cl´asica, las inserciones siempre van en las hojas y al borrar se reconstruye el sub´arbol borrado volvi´endolo a insertar en el lugar del nodo eliminado. En estos experimentos volvemos a utilizar el dise˜no de experimentos anterior pero ahora tambi´en los ejecutamos en las dem´as implementaciones. Esto significa que para cada dimensi´on k=2,3,4,5,6 calculamos el coste de crear el ´arbol, insertar llaves, y borrar llaves. Esto lo hacemos para cada tama˜no nde 25000 a 50000 en incrementos de 5000 generando 300 ´arboles de ese tama˜no. 37 Posteriormente, cuando el ´arbol es de tama˜no n, se realizan 6000 inserciones y 6000 borrados alternados, es decir, un borrado tras cada inserci´on y una inserci´on tras cada borrado. Este proceso se realiza para cada ´arbol y se cuentan los nodos visitados en la inserci´on y en el borrado y sus tiempos de ejecuci´on respectivos. Posteriormente se hace la media de cada inserci´on y borrado. 5.2.1 Coste de creaci´on Ahora veremos el coste en nodos visitados y en segundos de ejecuci´on durante la creaci´on de los ´arboles para las dimensiones de la 2 a la 6 separadamente. 38 Figura 24: Coste medio de creaci´on en nodos visitados para quad trees de dimensi´on k=2,3,4,5,6 y tama˜no nde 25000 a 50000 para los tres algoritmos distintos Como podemos ver el coste en nodos visitados entre nuestro algoritmo y el de la cola de prioridad parece ser el mismo mientras que el coste de la implementaci´on no randomizada es considerablemente menor. 39 Figura 25: Tiempo medio de creaci´on en segundos para quad trees de dimensi´on k=2,3,4,5,6 y tama˜no nde 25000 a 50000 para los tres algoritmos distintos El tiempo de ejecuci´on sigue siendo inferior en la no randomizada pero podemos observar como nuestra implementaci´on respecto a la de la cola de prioridad es m´as veloz para las dimensiones de la 2 a la 4 y m´as lenta en la dimensi´on 6. Esto puede deberse a que los nodos que deben ser remplazados tienen que atravesar caminos m´as largos cuando la dimensi´on es m´as peque˜na en el algoritmo de cola de prioridad mientras que no es el caso en la nuestra. 40 Figura 31: Planificaci´on final por semanas y tareas. El primer cambio que podemos apreciar es el movimiento de la tarea de documentaci´on al final de cada etapa. Nos dimos cuenta de que el trabajo que se pod´ıa avanzar documentando no era tan grande y que era necesario tener otras partes acabadas. Por otra parte, la implementaci´on y el dise˜no y an´alisis de experimentos ha supuesto m´as tiempo del esperado. La implementaci´on supuso primeramente implementar la propuesta original y al ver que no era eficiente se invirtieron un par de semanas en optimizar los c´odigos. Por otra parte hubo que implementar las otras dos propuestas y preparar todas las implementaciones para la fase experimental. El an´alisis de experimentos tuvo que ser repetido dado que la muestra inicialmente elegida no aportaba datos precisos. Por otra parte tambi´en se hicieron varias pruebas e experimentos que no dieron resultados concluyentes. Pese a estos retrasos, la fase de Estudio del estado del arte fue m´as r´apida de los esperado y las horas de conclusiones y ´ultimos retoques (cuyo objetivo 47 era representar un tiempo para cubrir posibles imprevistos) fueron suficientes para ser reasignadas a estas fases haciendo que el proyecto se completase en el periodo de tiempo esperado de 465h. Tarea Horas estimadas Horas reales Estudio del estado del arte 72 60 Implementaci´on 72 120 Dise˜no y an´alisis experimental 72 120 Conclusiones y ´ultimos retoques 78 0 Documentaci´on 156 150 Reuniones 15 15 Total 465 465 6.2 An´alisis econ´omico Ahora calcularemos el coste final del proyecto y las desviaciones respecto al presupuesto inicial. El presupuesto inicial del proyecto era de 21620e. De este presupuesto lo ´unico que ha sido modificado han sido la distribuci´on de las tareas realizadas. La distribuci´on de las horas finalmente queda de la siguiente manera: Fase J. de Proyecto Desarrollador Analista Total Estudio del estado del arte 60h 0h 0h 60h Implementaci´on 20h 100h 0h 120h Dise˜no y an´alisis experimental 20h 0h 100h 120h Documentaci´on 150h 0h 0h 150h Reuniones 15h 0h 0h 15h Total 265h 100h 100h 465h Despu´es de asignar el coste de hora correspondiente a cada tarea nos queda el coste total de personal: 48 Rol Coste/hora Horas Coste Jefe de proyecto 50e/h 265h 13250e Desarrollador 35e/h 100h 3500e Analista 30e/h 100h 3000e Total 19750e Los dem´as costes se mantienen igual. El coste de Hardware consiste en un port´atil y el Software es de libre distribuci´on. Los costes indirectos incluyen un espacio que incluye los costes de Internet, electricidad y mobiliario. A˜nadiendo estos costes nos queda el siguiente coste total: Concepto Coste Hardware 50e Software 0e Recursos humanos 19750e Costes indirectos 320e Total 20120e Ahora s´ı, podemos ver que la desviaci´on del coste del proyecto ha sido de 1500epor debajo del presupuesto y la desviaci´on en consumo ha sido nula dado que se han invertido el mismo n´umero de horas que el esperado. 49 7 Sostenibilidad 7.1 Dimensi´on ambiental El proyecto ha tenido un impacto ambiental m´ınimo. Se ha usado hardware reacondicionado para minimizar el da˜no ambiental que producen los deshechos tecnol´ogicos y la producci´on de nuevos dispositivos. Por otra parte, el consumo de electricidad ha sido tenido en cuenta. Si el ordenador consume una media de 100W y necesitamos 465h, entonces eso son 46,5KWh que equivalen a 17,9kg de CO2. Es una gran cantidad de energ´ıa pero es la necesaria para el desarrollo del proyecto. Durante la vida ´util del proyecto no se usar´an m´as recursos por nuestra parte. El proyecto ha tenido como finalidad publicar los algoritmos para el uso libre de estos y as´ı reducir los costes que conllevar´ıan a empresas e individuos reproducir los resultados. Todo ello conlleva una reducci´on del impacto negativo al medio ambiente. 7.2 Dimensi´on econ´omica Ya se ha presentado un an´alisis completo del presupuesto del proyecto. En la propuesta se ha tenido en cuenta los costes materiales al elegir software libre y hardware reacondicionado. El coste principal son recursos humanos. El problema actual se resuelve gastando recursos de manera privada en cada situaci´on que se necesita. Mi propuesta ofrece una alternativa gratuita. Esto comporta un ahorro significante a los usuarios que no tienen que invertir m´as recursos humanos de los necesarios. Por tanto, el ahorro futuro compensa esta inversi´on actual. Durante la vida ´util del proyecto no habr´an m´as costes econ´omicos por nuestra parte. 50 7.3 Dimensi´on social Este proyecto me ha aportado la capacidad de emprender proyectos y llevarlos de una forma correcta. Me ha ense˜nado a planificar el tiempo y estimar los recursos. As´ı como ver que imprevistos surgen durante la realizaci´on. Como ya hemos dicho el problema actual se resuelve de forma individual y privada. Nuestra propuesta permite a los usuarios ganar tiempo al tener los algoritmos p´ublicos. Por otra parte, el hecho de realizar el proyecto beneficia directamente a la comunidad de investigaci´on. Adem´as, el proyecto no perjudica a ning´un usuario ni les produce ninguna dependencia. 51 8 Conclusiones y trabajo futuro 8.1 Conclusiones En este proyecto hemos intentado implementar la propuesta Randomized insertion and deletion in point quad trees [4] y analizar experimentalmente su coste, especialmente el del borrado de nodos, y compararlo con el de algoritmos cl´asicos. Lo primero que vimos es que la implementaci´on tal como estaba descrita era muy ineficiente en la pr´actica y no pod´ıa competir con los algoritmos cl´asicos. Bas´andonos de los algoritmos propuestos en dicho art´ıculo se realiz´o una implementaci´on alternativa que puede ser optimizada en un futuro. Al realizar los experimentos vimos que los costes de inserci´on y borrado de esta implementaci´on podr´ıan ser del orden Θ(log(n) log(log(n))) mientras que el coste de los algoritmos aplicados a la ra´ız del ´arbol podr´ıan ser del orden Θ(nlog(n)). Al comparar la implementaci´on con una implementaci´on basada en una cola de prioridad vemos que el coste asint´otico parece ser el mismo y que temporalmente podr´ıa ser m´as r´apida nuestra implementaci´on para dimensiones menores a 5. Al comparar la implementaci´on con una implementaci´on cl´asica sin randomizar vemos que el coste de nuestra implementaci´on es menor en el borrado, pero cuando se mide el tiempo de ejecuci´on, la implementaci´on cl´asica tarda un tiempo similar. Aun as´ı, en nuestros experimentos los nodos insertados y borrados son aleatorios. Si no fuese as´ı, el coste del algoritmo cl´asico seria mayor y nuestra implementaci´on podr´ıa ser m´as r´apida, sobre todo si el input estuviese ordenado. 52 8.2 Trabajo futuro A partir de estas conclusiones, vemos que queda mucho trabajo interesante para hacer en este campo. Primeramente, nuestra implementaci´on propuesta en este proyecto podr´ıa ser mejorada. Por ejemplo, el algoritmo join elige el m´aximo linealmente y quiz´as se podr´ıa aprovechar alguna estrategia diferente para ahorrar costes. Adem´as, se podr´ıan aprovechar algunas propiedades de la definici´on de los quad trees (que a´un no han sido aprovechadas en nuestra implementaci´on) para ahorrar algunas comparaciones entre llaves. Aunque no era el objetivo inicial de este trabajo, podr´ıan estudiarse experimentalmente las varianzas de los costes de inserci´on y borrado y hacer un an´alisis estad´ıstico en mayor profundidad. Tambi´en ser´ıa muy interesante obtener el coste exacto de nuestras operaciones de inserci´on y borrado obtenido mediante c´alculos matem´aticos formales. Sin embargo, puede ser un problema dif´ıcil dado que las herramientas matem´aticas (combinatoria anal´ıtica) que se requieren para este tipo de an´alisis no son b´asicas. Dado que nuestros experimentos han trabajado con nodos insertados en orden aleatorio, podr´ıa probarse cu´al es el coste de tener un input ordenado y comparar los algoritmos randomizados aqu´ı propuestos contra la implementaci´on no randomizada usando un preprocesamiento del input que alterase el orden del input y ver si el tiempo de ejecuci´on sigue siendo mejor. Podr´ıa ser tambi´en interesante ver c´omo se desempe˜nan nuestros algoritmos con datos de aplicaciones reales, por ejemplo, datos provenientes de bases de datos gen´omicas que adem´as de contener grandes cantidades de puntos, son altamente multidimensionales (dimensi´on 19 en algunos casos) [6]. Para tener acceso al c´odigo y probar experimentos o mejoras, aqu´ı se encuentra el repositorio: https://bitbucket.org/Oliver_Mp0/randomized-quad-trees/src/master/ 53 Referencias [1] T. H. Cormen. Introduction to algorithms. MIT Press, 2001. [2] J. C. Culberson. The effect of updates in binary search trees. STOC ’85 Proceedings of the seventeenth annual ACM symposium on Theory of computing, 205-212, 1985. [3] L. Devroye and J. M. Robson. On the Generation of Random Binary Search Trees. SIAM J. Comput., 24(6), 1141–1156, 1995. [4] A. Duch. Randomized insertion and deletion in point quad trees. Departament de Llenguatges i Sistemes Inform`atics, Universitat Polit`ecnica de, Catalunya, Barcelona, Spain, 2004. [5] J. L. Eppinger. An empirical study of insertion and deletion in binary search trees. Communications of the ACM, 26(9):663-669, 1983. [6] 1000 Genomes Project Consortium et al. 2015. A global reference for human genetic variation. 7571, 68-74, 2015. [7] R. A. Finkel and J. L. Bentley. Quad trees: a data structure for retrieval on composite key. Acta Informatica, 4(1):1–9, 1974. [8] D. E. Knuth. The Art of Computer Programming: Sorting and Searching, volume 3. Addison–Wesley, 2nd edition, 1998. [9] C. Mart´ınez, A. Panholzer, and H. Prodinger. On the number of descendants and ascendants in random search trees. Electronic Journal on Combinatorics, 5(1), 1998. [10] C. Mart´ınez and S. Roura. Randomized binary search trees. Journal of the ACM, 45(2):288-323, 1998. [11] C. McGeoch. A Guide to Experimental Algorithmics. Cambridge University Press, 2012. [12] R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995. [13] H. Samet. Deletion in two-dimensional quad-trees. Communications of the ACM, 23(12):703–710, 1980. 54 [14] H. Samet. The Design and Analysis of Spatial Data Structures. Addison- Wesley, 1990. [15] H. Samet. Foundations of Multidimensional and Metric Data Structures. Morgan & Kaufman Publ., 2006. [16] R. Seidel and C. Aragon. Randomized search trees. Algorithmica 16, 464–497, 1996. 55