Representación de datos multidimensionales dispersos

Estoy trabajando en una herramienta de simulación cardíaca que utiliza datos de 4 dimensiones, es decir, varias variables (3-30) en ubicaciones en el espacio 3D.

Ahora estoy agregando algo de geometría de tejido que dejará más de 2/3 de los puntos en el cuadro 3D que contiene fuera del tejido que se va a simular, por lo que necesito una forma de almacenar de manera eficiente los puntos activos y no los otros.

De manera crucial, necesito poder:

  • Iterar sobre todos los puntos activos dentro de un cuadro 3D restringido (¿iterador, quizás?)
  • Habiendo accedido a un punto, encuentre sus vecinos ortogonales (x, y, z) +/- 1.

¡Eso es probablemente más que una pregunta! Mi principal preocupación es cómo representar eficientemente los datos dispersos.

Estoy usando C.

¿Con qué frecuencia agrega el tejido y cuánto tiempo puede tomar?

Una solución simple es usar una lista enlazada + hash con punteros de uno a otro.

Sentido:

  1. Guarda una lista enlazada que contiene todos los puntos relevantes y sus datos
  2. Guarde un hash para obtener fácilmente estos datos: clave = coordenadas, datos = puntero a la lista enlazada.

La implementación de las operaciones sería:
Agregue un cuadro: recorra la lista de enlaces completa y lleve solo los elementos relevantes a la lista de “trabajos”
Iterar: repasar la lista enlazada de “trabajo”
Encuentra vecinos: busca a cada uno de los vecinos en el hachís.

Complejidad:
Agregue: O (n), Iterate O (1) para encontrar el siguiente elemento, Vecino O (1) promedio (debido al hash).

Si desea utilizar la indexación de matriz plana, puede crear una matriz dispersa en sistemas POSIX utilizando mmap ():

float (*a)[500][500]; a = mmap(0, (size_t)500 * sizeof a[0], PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0); if (a && (void *)a != MAP_FAILED) { /* a is now 500 x 500 x 500 sparse array of floats */ 

Luego puede acceder a una [x] [y] [z] como desee, y solo asignará memoria real para cada página que toque. La matriz se inicializará a cero bytes.

Si su sistema no tiene MAP_ANONYMOUS, puede lograr el mismo efecto asignando desde / dev / zero.

Tenga en cuenta que en muchos sistemas, el espacio de intercambio se reservará (aunque no se utilizará) para toda la matriz.

En primer lugar, creo que vale la pena considerar cuál es su requisito real. Sospecho que no solo se trata de “almacenar los puntos activos y ninguno de los demás de la manera más eficiente en espacio posible”, sino también una cierta cantidad de “almacenar puntos adyacentes en ubicaciones de memoria cercanas para que obtenga un buen comportamiento de almacenamiento en caché” y “almacenar puntos de una manera para que las búsquedas se pueden hacer de manera eficiente”.

Dicho esto, esto es lo que sugeriría. Divide la región 3D completa en bloques cúbicos, todos del mismo tamaño. Para cada bloque, almacene todos los puntos en el bloque en matrices densas, incluida una matriz de tejidos iso booleanos para determinar si cada punto está en la región del tejido o no. Asigna solo los bloques que tienen puntos en ellos. Haga una matriz (densa) de punteros a bloques, con punteros NULL para bloques no asignados.

Por lo tanto, para encontrar el punto en (i, j), primero calcule ii = i / blockside, jj = j / blockize, y luego mire en la tabla de puntero a bloque en (ii, jj) para encontrar el bloque que contiene tu punto Si ese puntero es NULO, su punto no está en el tejido. Si no es nulo, observa (i mod blocksize, j mod blocksize) en ese bloque, y ahí está tu (i, j) punto. Puede verificar su indicador de Tejido para ver si es un punto “presente” o no.

Querrá elegir el tamaño de bloque como un equilibrio entre minimizar el número de veces que realiza cálculos de puntos adyacentes que cruzan los límites de los bloques y minimizar el número de puntos que están en bloques pero no en la región del tejido. Supongo que, como mínimo, desea que una fila del bloque sea una línea de caché larga. Probablemente el óptimo sea más grande que eso, aunque dependerá al menos un poco de su geometría.

Para recorrer en iteración todos los puntos en un cuadro 3D, solo debe hacer búsquedas para cada punto o (más eficientemente) averiguar qué bloques toca el cuadro, e iterar sobre las regiones en esos bloques que están dentro de su cuadro, omitiendo el unos donde isTissue is false.

Si está realizando una gran cantidad de desasignación y reasignación de bloques, probablemente desee “desasignar” los bloques colocándolos en un grupo “no utilizado” y luego retirando los bloques de ese grupo en lugar de reasignarlos. Esto también tiene la ventaja de que esos bloques ya tendrán todos sus puntos configurados en “no presente” (porque es por eso que desasignó el bloque), por lo que no necesita inicializarlos.

El lector experimentado probablemente reconocerá las similitudes entre esto y las formas de distribución de datos para cálculos paralelos; Si tiene una simulación realmente grande, puede distribuir fácilmente los bloques a través de múltiples nodos, y solo necesita hacer comunicación entre nodos para los cálculos de bloques cruzados. Para ese tipo de aplicación, puede resultarle útil hacer niveles de bloques nesteds, donde tiene metabloques (para la comunicación entre nodos) que contienen bloques más pequeños (para la geometría).