You are currently browsing the category archive for the ‘Estructuras de Datos’ category.

En el método SPH necesitamos conocer cual es su conjunto de vecinos de una partícula a. Este viene determinado por la smoothing length h, uno de los parámetros de las funciones kernel.

Supongamos que tenemos N partículas. Si N es lo suficientemente pequeño, lo único que tenemos que hacer es, para cada partícula, recorrer el resto de partículas calculando su distancia a nuestra partícula y tener en consideración solo aquellas que esten a distancia menor que h (all-pair search). La complejidad del algorítmo es O(N^2).

Sin embargo, cuando el número de partículas crece, y que lo ha de hacer pues en eso se basa la potencia del método, esta manera de trabajar es mejorable.

A continuación veremos algunas opciones, pero la idea general es que necesitamos tener una descomposición espacial de nuestro escenario que nos permita encontrar de manera eficiente el vecindario de cada una de nuestras partículas y que tendremos que mantener actualizada a medida que evoluciona el sistema.

Otra opción es la linked-list. Se trata de superponer una malla con un tamaño de celda 2h, de manera que, dada una partícula, solo tendremos que buscar las partículas que se encuentran en las celdas adyacentes. En C++ tenemos las clases list y vector. La primera por nombre y la segunda porque la clase vector puede crecer dinámicamente. Solo podremos utilizarlas si la h es constante para todas las partículas. La complejidad, con un número suficientemente pequeño de partículas por celda, es O(N).

Finalmente, podemos trabajar con árboles. Los árboles permiten complejidades genéricas en búsquedas de O(N \log N) y permiten trabajar con h diferentes para cada partícula. En astrofísica, por ejemplo, podríamos tener un arbol binario de búsqueda, pues tenemos que simular objetos autogravitantes y necesitamos resolver un problema de n-cuerpos, que parece ser que es lo que mas tiempo de CPU consume. Para hacer esto de manera eficiente necesitamos un BST. Se trata de utilizar este mismo para realizar las búsquedas. La clase map de C++ se implementa con un arbol binario balanceado (AVL).

Existen otras estructuras de datos que permiten hacer descomposiones espaciales que podria ser interesante analizar (UB-tree, Octrees, BST, kd-tree, R-tree).

Anuncios
diciembre 2017
L M X J V S D
« Ago    
 123
45678910
11121314151617
18192021222324
25262728293031