Spärliche multidimensionale Datenrepräsentation

Question

Ich arbeite an einem Herzsimulationswerkzeug, das 4-dimensionale Daten verwendet, d. H. Mehrere (3-30) Variablen an Stellen im 3D-Raum.

Ich füge nun eine Gewebegeometrie hinzu, die mehr als 2/3 der Punkte in der 3D-Box außerhalb des zu simulierenden Gewebes belässt, also brauche ich eine Möglichkeit, die aktiven Punkte effizient zu speichern und nicht die anderen .

Entscheidend ist, muss ich in der Lage:

• Iterate über alle aktiven Stellen innerhalb eines eingeschränkten 3D-Box (Iterator, vielleicht?)
• einen Punkt erreicht haben, seine orthogonalen Nachbarn finden (x, y, z) +/- 1.

Das ist wahrscheinlich mehr als eine Frage! Mein Hauptanliegen ist, wie man die spärlichen Daten effizient darstellt.

Ich verwende C.

Answer 1

Wie oft Sie das Gewebe hinzufügen, und wie viel Zeit kann es dauern?

Eine einfache Lösung ist eine verkettete Liste + Hash mit Zeigern von einem zum anderen.

Bedeutung:

1. Speichern eine verknüpfte Liste alle relevanten Punkte und deren Daten
2. Speichern ein Hash enthält, leicht auf diese Daten zu erhalten: key = Koordinaten, Daten = Zeiger auf die verknüpften Liste.

Die Durchführung der Maßnahmen wäre:
hinzufügen Box: Go über die volle Liste verknüpft, und nur die relevanten Elemente in die „Arbeit“ verketteten Liste
Iterate nehmen: Fahren Sie über die verknüpfte Liste "Arbeit"
Nachbarn finden: Sucht jeden der Nachbarn im Hash.

Komplexität:
Hinzufügen: O (n), Iterate O (1) zum Finden des nächsten Elements, Nachbar O (1) Durchschnitt (wegen Hash).

Answer 2

Wenn Sie Normal Array-Indizierung verwenden möchten, können Sie eine spärliche Array auf POSIX-Systemen unter Verwendung von mmap() erstellen:

float (*a)[500][500]; 

a = mmap(0, (size_t)500 * sizeof a[0], PROT_READ | PROT_WRITE, 
    MAP_PRIVATE | MAP_ANONYMOUS, -1, 0); 

if (a && (void *)a != MAP_FAILED) 
{ 
    /* a is now 500 x 500 x 500 sparse array of floats */ 

Sie können dann auf nur einen [x] [y] [z] als Sie mögen, und es wird nur tatsächlich Speicher für jede Seite, die berührt wird, zuweisen. Das Array wird auf Null Bytes initialisiert.

Wenn Ihr System MAP_ANONYMOUS nicht besitzt, können Sie den gleichen Effekt erzielen, indem Sie von/dev/zero mappen.

Beachten Sie, dass Swap Space auf vielen Systemen für das gesamte Array reserviert (aber nicht verwendet) wird.

Answer 3

Zunächst einmal, ich denke, es ist eine Überlegung wert, was Ihre wirkliche Anforderung ist.Ich vermute, dass es nicht nur ist, "die aktiven Punkte und keine der anderen so platzsparend wie möglich zu speichern", sondern auch eine gewisse Menge an "benachbarten Punkten in nahegelegenen Speicherorten zu speichern, damit Sie ein gutes Caching-Verhalten bekommen" und "speichert Punkte in einer Weise, für die Nachschläge effizient durchgeführt werden können".

Mit diesem gesagt, hier ist, was ich vorschlagen würde. Teilen Sie die gesamte 3D-Region in kubische Blöcke gleicher Größe auf. Speichern Sie für jeden Block alle Punkte im Block in dichten Arrays, einschließlich eines booleschen isTissue-Arrays, ob sich jeder Punkt in der Gewebezone befindet oder nicht. Ordnen Sie nur die Blöcke zu, die Punkte enthalten. Erstellen Sie ein (dichtes) Array von Zeigern auf Blöcke mit NULL-Zeigern für nicht zugeordnete Blöcke.

Um also den Punkt bei (i, j) zu finden, berechnen Sie zunächst ii = i/blockside, jj = j/blocksize, und dann in der Pointer-to-Block-Tabelle bei (ii, jj) nach finde den Block, der deinen Punkt enthält. Wenn dieser Zeiger NULL ist, ist Ihr Punkt nicht im Gewebe. Wenn es nicht null ist, sehen Sie (i mod blocksize, j mod blocksize) in diesem Block, und da ist Ihr Punkt (i, j). Sie können sein isTissue-Flag überprüfen, um zu sehen, ob es ein "gegenwärtiger" Punkt ist oder nicht.

Sie sollten die Blockgröße als Ausgleich zwischen der Minimierung der Anzahl der Berechnungen benachbarter Punkte, die Blockgrenzen überschreiten, und der Minimierung der Anzahl der Punkte in Blöcken, aber nicht im Gewebebereich, wählen. Ich nehme an, dass mindestens eine Zeile des Blocks eine Cache-Zeile lang sein soll. Wahrscheinlich ist das Optimum eher größer als das, obwohl es zumindest etwas von Ihrer Geometrie abhängen wird.

Um über alle Punkte in einer 3D-Box zu iterieren, würden Sie entweder nur nach jedem Punkt suchen oder (effizienter) herausfinden, welche Blöcke die Box berührt und iterieren über die Bereiche in diesen Blöcken Box, überspringt die, wo isTissue falsch ist.

Wenn Sie viele Zuweisungen und Neuzuweisungen von Blöcken durchführen, möchten Sie wahrscheinlich Blöcke "aufheben", indem Sie sie in einen "unbenutzten" Pool ablegen und dann Blöcke aus diesem Pool herausziehen, anstatt sie neu zuzuweisen . Dies hat auch den Vorteil, dass für diese Blöcke bereits alle Punkte auf "nicht vorhanden" gesetzt sind (weil Sie den Block deshalb deklariert haben), so dass Sie sie nicht initialisieren müssen.

Der erfahrene Leser wird wahrscheinlich Ähnlichkeiten zwischen diesen und Möglichkeiten zum Auslegen von Daten für parallele Berechnungen erkennen; Wenn Sie eine wirklich große Simulation haben, können Sie die Blöcke problemlos über mehrere Knoten verteilen, und Sie müssen nur für die Kreuzblockberechnungen übergreifend kommunizieren. Für diese Art von Anwendung kann es nützlich sein, verschachtelte Ebenen von Blöcken zu machen, bei denen Sie Metablöcke (für die Kreuzknoten-Kommunikation) mit kleineren Blöcken (für die Geometrie) haben.