Wydajna struktura do reprezentowania hierarchii transformacji

Czy ktoś może zasugerować efektywny sposób pamięci do reprezentowania drzewa macierzy, na przykład w modelu hierarchicznym?

Szczególnie zależy mi na zachowaniu lokalizacji danych i podejrzewam, że odpowiednie może być podejście typu struktura tablic (macierze i wskaźniki do macierzy).

Oprócz wielu łańcuchowych obliczeń macierzowych, ta struktura prawdopodobnie zostanie skopiowana do pamięci całkiem sporo, więc posiadanie ciągłej pamięci byłoby dużą zaletą.

memory-efficiency tree

— Justicle
źródło

Drzewo jak tablica brzmi dla mnie jak wygrana. Po prostu wykonaj głębokie przemierzanie swojej hierarchii i wypełnij tablicę; podczas przewijania przez rekurencję możesz albo zaktualizować element nadrzędny z indeksem bezwzględnym do elementu podrzędnego, albo po prostu delta-od-mnie, a dzieci mogą również przechowywać indeksy nadrzędne w dowolny sposób. Rzeczywiście, jeśli użyjesz względnych przesunięć, nie musisz nosić adresu głównego. Przypuszczam, że struktura prawdopodobnie wyglądałaby podobnie

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

... więc potrzebujesz węzłów, aby wiedzieć, jak dostać się do rodzeństwa, ponieważ nie możesz (łatwo) mieć struktury o zmiennym rozmiarze. Chociaż myślę, że jeśli użyłeś przesunięć bajtów zamiast przesunięć transformacji, możesz mieć zmienną liczbę dzieci na transformację:

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

... musisz tylko upewnić się, że umieszczasz kolejne Transformacje we właściwym miejscu.

Oto jak zbudować całkowicie samodzielne drzewo z osadzonymi „wskaźnikami” dla dzieci.

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

(Jeśli chcesz przechowywać względne lokalizacje, po prostu dodaj - currentLocationdo dwóch zapisów „lokalizacja”).

— dash-tom-bang
źródło

Jeśli mówimy o C ++, musisz określić rozmiar tablicy podrzędnej lub utworzyć ją w czasie wykonywania z alokacją pamięci.

— tenpn

Oficjalnym sposobem C99 jest pozostawienie pustej specyfikacji rozmiaru tablicy.

@ tenpn - chodzi o to, że masz bufor zbudowany. Chodzi o to, aby uniknąć dodatkowych przydziałów; nie możesz określić rozmiaru tablicy, ponieważ nie wiesz, jak duży będzie. Po napisaniu liczby dzieci zapisujesz w tablicy podrzędnej, ale następna transformacja rozpoczyna się po zakończeniu tablicy podrzędnej. (Dlatego właśnie w tej strukturze należy używać przesunięć bajtów, a nie indeksów; nie wiesz, jak duże są poszczególne wpisy, ale nadal jest efektywne przechodzenie i samodzielne, dzięki czemu może się poruszać jako jednostka.)

— myślnik -tom-bang

Nazywa się to „struct hack”. Zobacz także: informit.com/guides/content.aspx?g=cplusplus&seqNum=288

— Neverender

@tenpn Aka struktury o zmiennej długości. Odpowiednio użyte mogą zmniejszyć o połowę liczbę przydziałów sterty.

Indeksowanie w macierz macierzy byłoby prawdopodobnie najprostszym i najbardziej wydajnym podejściem do pamięci.

Łańcuch transformacji może być przechowywany w LIFO jako seria wskaźników lub liczb całkowitych lub innej małej struktury, która indeksuje się do macierzy macierzy. Pomoże to zapobiec przechowywaniu zbędnych matryc i oddzieli kod przechowywania danych od kodu dostępu do danych.

Ostatecznie wystarczy popchnąć i wyskoczyć wartości indeksu z LIFO, aby zapisać lub odtworzyć łańcuch transformacji.

Możesz również zaoszczędzić trochę pamięci, jeśli struktura macierzy może również zawierać typ transformacji ... obrót, translację itp. W przeciwnym razie typ musiałby być zapisany z indeksem, co spowodowałoby większą możliwą duplikację.

— Zardzewiały
źródło