Matrices tridimensionales computacionalmente eficientes en C

Question

Estoy intentando resolver numéricamente un conjunto de ecuaciones diferenciales parciales en tres dimensiones.En cada una de las ecuaciones el siguiente valor de la incógnita en un punto depende del valor actual de cada incógnita en los puntos más cercanos.

Para escribir un código eficiente, necesito mantener los puntos cercanos en las tres dimensiones en el espacio de memoria (unidimensional), de modo que cada valor se llame desde la memoria solo una vez.

Estaba pensando en usar octtrees, pero me preguntaba si alguien conoce un método mejor.

Answer 1

Los octtrees son el camino a seguir.Subdivides la matriz en 8 octantes:

1 2
3 4

---

5 6
7 8

Y luego colóquelos en la memoria en el orden 1, 2, 3, 4, 5, 6, 7, 8 como se indica arriba.Repite esto de forma recursiva dentro de cada octante hasta llegar a un tamaño base, probablemente alrededor de 128 bytes (esto es solo una suposición; asegúrese de crear un perfil para determinar el punto de corte óptimo).Esto tiene una coherencia de caché y una localidad de referencia mucho mejores que el diseño ingenuo.

Answer 2

Una alternativa al método del árbol:Utilice Morton-Order para codificar sus datos.

En tres dimensiones es así:Tome los componentes de coordenadas e intercale cada bit con dos bits cero.Aquí se muestra en binario:11111b se convierte en 1001001001b

Una función C para hacer esto se ve así (se muestra para mayor claridad y solo para 11 bits):

int morton3 (int a)
{
  int result = 0;
  int i;
  for (i=0; i<11; i++)
  {
     // check if the i'th bit is set.
     int bit = a&(1<<i);
     if (bit)
     {
       // if so set the 3*i'th bit in the result:
       result |= 1<<(i*3);
     }
  }
  return result;
}

Puede utilizar esta función para combinar sus posiciones de esta manera:

index = morton3 (position.x) + 
        morton3 (position.y)*2 +
        morton3 (position.z)*4;

Esto convierte su índice tridimensional en uno unidimensional.Lo mejor de esto:Los valores que están cerca en el espacio 3D también lo están en el espacio 1D.Si accede con frecuencia a valores cercanos entre sí, también obtendrá una muy buena aceleración porque la codificación de orden morton es óptima en términos de localidad de caché.

Para morton3 es mejor que no uses el código anterior.Utilice una tabla pequeña para buscar 4 u 8 bits a la vez y combinarlos.

Espero que ayude, nils

Answer 3

El libro Fundamentos de estructuras de datos métricos y multidimensionales puede ayudarle a decidir qué estructura de datos es más rápida para consultas de rango:octrees, kd-trees, R-trees, ...También describe diseños de datos para mantener puntos juntos en la memoria.