Matrizes tridimensionais computacionalmente eficientes em C

Question

Estou tentando resolver numericamente um conjunto de equações diferenciais parciais em três dimensões.Em cada uma das equações o próximo valor da incógnita num ponto depende do valor atual de cada incógnita nos pontos mais próximos.

Para escrever um código eficiente preciso manter os pontos próximos nas três dimensões próximos no espaço de memória (unidimensional), para que cada valor seja chamado da memória apenas uma vez.

Eu estava pensando em usar octtrees, mas queria saber se alguém conhece um método melhor.

Answer 1

Octtrees são o caminho a percorrer.Você subdivide a matriz em 8 octantes:

1 2
3 4

---

5 6
7 8

E então organize-os na memória na ordem 1, 2, 3, 4, 5, 6, 7, 8 conforme acima.Você repete isso recursivamente dentro de cada octante até chegar a um tamanho base, provavelmente em torno de 128 bytes ou mais (isso é apenas um palpite - certifique-se de criar um perfil para determinar o ponto de corte ideal).Isso tem coerência de cache e localidade de referência muito, muito melhores do que o layout ingênuo.

Answer 2

Uma alternativa ao método da árvore:Use o Morton-Order para codificar seus dados.

Em três dimensões é assim:Pegue os componentes de coordenadas e intercale cada bit com dois bits zero.Aqui mostrado em binário:11111b torna-se 1001001001b

Uma função C para fazer isso é semelhante a esta (mostrada para maior clareza e apenas 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;
}

Você pode usar esta função para combinar suas posições assim:

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

Isso transforma seu índice tridimensional em unidimensional.A melhor parte disso:Valores próximos no espaço 3D também estão próximos no espaço 1D.Se você acessar valores próximos uns dos outros com frequência, também obterá uma aceleração muito boa porque a codificação da ordem morton é ideal em termos de localidade do cache.

Para morton3 é melhor não usar o código acima.Use uma pequena tabela para procurar 4 ou 8 bits por vez e combiná-los.

Espero que ajude, nils

Answer 3

O livro Fundamentos de estruturas de dados multidimensionais e métricas pode ajudá-lo a decidir qual estrutura de dados é mais rápida para consultas de intervalo:octrees, árvores kd, árvores R, ...Também descreve layouts de dados para manter os pontos juntos na memória.