Array tridimensionali computazionalmente efficienti in C

Question

Sto cercando di risolvere numericamente un insieme di equazioni alle derivate parziali in tre dimensioni.In ciascuna delle equazioni il valore successivo dell'incognita in un punto dipende dal valore attuale di ciascuna incognita nei punti più vicini.

Per scrivere un codice efficiente ho bisogno di mantenere i punti vicini nelle tre dimensioni vicini nello spazio di memoria (monodimensionale), in modo che ogni valore venga chiamato dalla memoria una sola volta.

Stavo pensando di usare Octtree, ma mi chiedevo se qualcuno conosce un metodo migliore.

Answer 1

Gli Octtree sono la strada da percorrere.Suddividi l'array in 8 ottanti:

1 2
3 4

---

5 6
7 8

E poi disponili in memoria nell'ordine 1, 2, 3, 4, 5, 6, 7, 8 come sopra.Lo ripeti ricorsivamente all'interno di ciascun ottante finché non raggiungi una dimensione di base, probabilmente circa 128 byte circa (questa è solo un'ipotesi: assicurati di profilare per determinare il punto di interruzione ottimale).Questo ha una coerenza della cache e una località di riferimento molto, molto migliori rispetto al layout ingenuo.

Answer 2

Un'alternativa al metodo dell'albero:Usa l'Ordine Morton per codificare i tuoi dati.

In tre dimensioni funziona così:Prendi i componenti delle coordinate e interlaccia ogni bit con due bit zero.Qui mostrato in binario:11111b diventa 1001001001b

Una funzione C per fare ciò assomiglia a questa (mostrata per chiarezza e solo per 11 bit):

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;
}

Puoi utilizzare questa funzione per combinare le tue posizioni in questo modo:

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

Questo trasforma il tuo indice tridimensionale in uno dimensionale.La parte migliore:I valori vicini nello spazio 3D sono vicini anche nello spazio 1D.Se accedi frequentemente a valori vicini tra loro otterrai anche una notevole accelerazione perché la codifica morton-order è ottimale in termini di località della cache.

Per morton3 è meglio non usare il codice sopra.Usa un tavolino per cercare 4 o 8 bit alla volta e combinarli insieme.

Spero che aiuti, zero

Answer 3

Il libro Fondamenti di strutture dati multidimensionali e metriche può aiutarti a decidere quale struttura dati è più veloce per le query di intervallo:octre, kd-tree, R-tree, ...Descrive inoltre la disposizione dei dati per tenere insieme i punti in memoria.