Effiziente Struktur zur Darstellung einer Transformationshierarchie

9

Kann jemand eine speichereffiziente Methode vorschlagen, um einen Matrizenbaum darzustellen, beispielsweise in einem Hierarchiemodell?

Ich bin besonders daran interessiert, die Datenlokalität zu erhalten, und ich vermute, dass ein Ansatz vom Typ der Struktur von Arrays (Matrizen & Indizes zu Matrizen) geeignet sein könnte.

Neben vielen verketteten Matrixberechnungen wird diese Struktur wahrscheinlich ein gutes Stück im Speicher kopiert, sodass ein zusammenhängender Speicher ein großer Bonus wäre.

Justicle
quelle

Antworten:

6

Der Tree-as-Array klingt für mich wie ein Gewinn. Führen Sie einfach eine Tiefenüberquerung Ihrer Hierarchie durch und füllen Sie ein Array aus. Beim Zurückspulen durch die Rekursion können Sie entweder das übergeordnete Element mit dem absoluten Index für das untergeordnete Element oder nur das Delta von mir aktualisieren, und die untergeordneten Indizes können die übergeordneten Indizes auch in beiden Richtungen speichern. Wenn Sie relative Offsets verwenden, müssen Sie die Stammadresse nicht mit sich herumtragen. Ich nehme an, dass die Struktur wahrscheinlich so aussehen würde

struct Transform
{
   Matrix m; // whatever you like
   int parent;   // index or offset, you choose!
   int sibling;
   int firstchild;
};

... Sie benötigen also Knoten, um zu wissen, wie Sie auch zu Geschwistern gelangen, da Sie (einfach) keine Struktur mit variabler Größe haben können. Obwohl ich denke, wenn Sie Byte-Offsets anstelle von Transformations-Offsets verwenden, können Sie eine variable Anzahl von untergeordneten Elementen pro Transformation haben:

struct Transform
{
   Matrix m; // whatever you like
   int parent;  // negative byte offest
   int numchildren;
   int child[0]; // can't remember if you put a 0 there or leave it empty;
                 // but it's an array of positive byte offsets
};

... dann müssen Sie nur noch sicherstellen, dass Sie aufeinanderfolgende Transformationen an der richtigen Stelle platzieren.

Hier erfahren Sie, wie Sie einen völlig eigenständigen Baum mit eingebetteten untergeordneten "Zeigern" erstellen.

int BuildTransforms(Entity* e, OutputStream& os, int parentLocation)
{
    int currentLocation = os.Tell();

    os.Write(e->localMatrix);
    os.Write(parentLocation);
    int numChildren = e->GetNumChildren();
    os.Write(numChildren);

    int childArray = os.Tell();
    os.Skip(numChildren * sizeof(int));
    os.AlignAsNecessary();  // if you need to align transforms

    childLocation = os.Tell();
    for (int i = 0; i < numChildren; ++i) {
        os.Seek(childArray + (i * sizeof(int)));
        os.Write(childLocation);
        os.Seek(childLocation);
        childLocation = BuildTransforms(e->GetChild(i), os, currentLocation);
    }

    return os.Tell();
}

void BuildTransforms(Entity* root)
{
    OutputStream os;
    BuildTransforms(root, os, -1, 0);
}

(Wenn Sie relative Speicherorte speichern möchten, fügen Sie einfach - currentLocationdie beiden "Standort" -Schreibvorgänge hinzu.)

Dash-Tom-Bang
quelle
Wenn es sich um C ++ handelt, müssen Sie eine Größe für Ihr untergeordnetes Array angeben oder es zur Laufzeit mit einer Speicherzuordnung erstellen.
Tenpn
Die offizielle C99-genehmigte Methode besteht darin, die Array-Größenangabe leer zu lassen.
@ tenpn- Die Idee ist, dass Sie einen speziell erstellten Puffer haben. Der springende Punkt ist, zusätzliche Zuweisungen zu vermeiden ; Sie können die Arraygröße nicht angeben, da Sie nicht wissen, wie groß sie sein wird. Nachdem Sie num child geschrieben haben, schreiben Sie in Ihr untergeordnetes Array. Die nächste Transformation beginnt jedoch nach dem Ende des untergeordneten Arrays. (Aus diesem Grund müssen Sie für diese Struktur Byte-Offsets und keine Indizes verwenden. Sie wissen nicht, wie groß jeder Eintrag ist, aber es ist immer noch effizient zu durchlaufen und in sich geschlossen, damit er sich als Einheit bewegen kann.)
Strich -tom-bang
1
Dies wird als "Struktur-Hack" bezeichnet. Siehe auch: informit.com/guides/content.aspx?g=cplusplus&seqNum=288
Neverender
1
@tenpn Aka Strukturen mit variabler Länge. Bei sachgemäßer Verwendung können sie die Anzahl der Heap-Zuordnungen halbieren.
1

Die Indizierung in ein Array von Matrizen wäre wahrscheinlich der einfachste und speichereffizienteste Ansatz.

Eine Kette von Transformationen könnte in einem LIFO als eine Reihe von Zeigern oder ganzen Zahlen oder einer anderen kleinen Struktur gehalten werden, die in das Matrixarray indiziert. Dies würde dazu beitragen, das Speichern redundanter Matrizen zu verhindern und den Datenspeichercode vom Datenzugriffscode zu trennen.

Letztendlich würden Sie nur Indexwerte aus dem LIFO pushen und einfügen, um Ihre Transformationskette zu speichern oder wiederzugeben.

Möglicherweise können Sie auch ein wenig Speicherplatz sparen, wenn Ihre Matrixstruktur auch den Transformationstyp ... Rotation, Translation usw. enthalten könnte. Andernfalls müsste der Typ mit dem Index gespeichert werden, was zu einer möglichen Duplizierung führen könnte.

rostig
quelle