una - que es un array en programacion

Arrays tridimensionales computacionalmente eficientes en C

Question

Estoy tratando de resolver numéricamente un conjunto de ecuaciones diferenciales parciales en tres dimensiones. En cada una de las ecuaciones, el siguiente valor de lo desconocido en un punto depende del valor actual de cada desconocido en los puntos más cercanos.

Para escribir un código eficiente, necesito mantener los puntos cercanos en las tres dimensiones cercanas al 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

El libro Fundamentos de estructuras de datos multidimensionales y métricas puede ayudarlo 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 los puntos juntos en la memoria.

Answer 2

Octtrees son el camino a seguir. Usted subdivide 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. Repita esto recursivamente dentro de cada octante hasta que llegue a un tamaño de base, probablemente alrededor de 128 bytes más o menos (esto es solo una suposición - asegúrese de que el perfil determine el punto de corte óptimo). Esto tiene mucha, mucha mejor coherencia de caché y lugar de referencia que el diseño ingenuo.

Answer 3

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

En tres dimensiones, dice así: tome los componentes de coordenadas y entrelaze cada bit 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 por claridad y solo por 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 usar 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. La mejor parte: los valores que están cerca en el espacio 3D también están cerca en el espacio 1D. Si accede a valores cercanos entre sí con frecuencia 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 de arriba. Use una tabla pequeña para buscar 4 u 8 bits a la vez y combínelos.

Espero que ayude, Nils