Rechnerisch effizient dreidimensionale Arrays in C

Question

Ich versuche, numerisch eine Reihe von partiellen Differentialgleichungen in drei Dimensionen zu lösen. In jeder der Gleichungen der nächste Wert des Unbekannten in einem Punkt ist abhängig von dem aktuellen Wert jedes unbekannten in den nächsten Punkten.

Um einen effizienten Code zu schreiben, ich brauche die Punkte zu halten dicht in den drei Dimensionen der Nähe des (eindimensionale) Speicherplatz, so dass jeder Wert aus dem Speicher aufgerufen wird, nur einmal.

Ich dachte octtrees zu verwenden, aber ich frage mich, ob jemand eine bessere Methode kennt.

Answer 1

Octtrees ist der Weg zu gehen. Sie unterteilen das Array in 8 Oktanten:

1 2
3 4

---

5 6
7 8

1 und diese in der Reihenfolge im Speicher dann auslegen, 2, 3, 4, 5, 6, 7, 8, wie oben. Sie wiederholen diese innerhalb jeden Oktanten rekursiv, bis zu einem gewissen Basisgröße herunterkommen, wahrscheinlich um 128 Bytes oder so (dies ist nur eine Vermutung ist - stellen Sie sicher, um den optimalen Cutoff-Punkt zu bestimmen, zum Profil). Dies hat viel, viel besser Cache-Kohärenz und Referenzlokalität als das naive Layout.

Answer 2

Eine Alternative zu der Baum-Methode. Verwenden Sie die Morton-Order Ihre Daten zu codieren

In drei Dimension geht es wie folgt aus: die Komponenten koordinieren nehmen und jedes Bit zwei Null-Bits verschachteln. Hier in binär dargestellt: 11111b wird 1001001001b

Eine C-Funktion, dies zu tun sieht wie folgt aus (aus Gründen der Klarheit gezeigt und nur für 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;
}

Sie können diese Funktion verwenden, um Ihre Positionen wie folgt kombiniert werden:

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

Damit wird Ihren dreidimensionalen Index in einen eindimensionalen ein. Bester Teil davon: Werte, die im 3D-Raum nahe sind in der Nähe in 1D Raum als auch. Wenn Sie Werte nahe beieinander liegen Zugriff häufig werden Sie auch ein sehr schönes Speed-up bekommen, weil die morton Ordnung Codierung in Bezug auf dem Cache-Ort optimal ist.

Für morton3 Sie besser nicht den oben stehenden Code verwenden. Verwenden Sie eine kleine Tabelle nachschlagen 4 oder 8 Bits zu einer Zeit, und kombinieren sie zusammen.

Hoffe, es hilft,   Nils

Answer 3

Das Buch Foundations of Multidimensional und Metric Datenstrukturen helfen können Sie entscheiden, welche Datenstruktur ist am schnellsten für Bereichsabfragen: Octrees, kd-Bäume, R-Bäume, ... Es beschreibt auch Datenlayouts für Punkte zusammen im Speicher zu halten.