Dwuwymiarowe tablice dynamiczne

Potrzebuje jakiejś ciekawej, prostej i optymalnej implementacji tablicy dwuwymiarowej do przechowywania prostych elementów lub wskaźników. Najprostszym rozwiązaniem byłoby wykorzystanie kontenerów z STL:

std::vector<std::vector<Element*> > array

Szybko i prosto, tylko używać.

Ale pojawia się problem, bo chciałbym, aby pojedyncza linia zachowywała się jak czysta tablicą w stylu C (wymagania API).

Także można by bez problemu zastosować vectora w vectorze, ale… ale o tym później.

Moja obecna i pierwsza implementacja takiego kontenera oparta jest na vektorze, który zawiera wskaźnik na alokowana dynamicznie tablice wskaźników do elementów. Wstawianie elementów do nowego wiersza wyglądałoby tak:

// dodanie elementu do nowego wiersza
void push_back_row(Element* item) {
	Element** row = new Element*[m_RowsSize];
	row[0] = item;
	m_lines.push_back(row);
}

Jako tako działa to dobrze. Zrobiłem sobie nawet prosta strukturę typu index, do łatwiejszego operowania na indeksach, a także poziome wstawianie elementów wierszami.

Tylko jedne problem, jakby popatrzeć, standardowa implementacja operatora new nie jest wydajna i optymalna dla alokowania małych bloków pamięci (< 64 bajty). A jak wspomniałem, nasza tablica zawierałaby tylko kilka wskaźników, przyjmijmy, że defaultowo 4 (4 elementy na wiersz) co daje 16 bajtów. Alokowanie 16 bajtów przy hurtowym wstawianiu elementów i wiersza będzie bardzo mało wydajne.

Tak, wiec przechodzimy do kolejnego rozwiązania.

Alokujemy sobie 400 elementową jednowymiarową tablicę dla 100 wierszy po 4 elementy (wskaźniki), co daje nam 400 bajtów. Tworzymy sobie vektora na wskaźniki do wskaźników elementów (Element**) i rezerwujemy na 100 elementów. Każda wiersz, czyli element vectora będzie wskazywał na odpowiednią pozycję w zaalokowanej jednowymiarowej tablicy (co 4 element). Oczywiście wskaźniki te będą dodawane automatycznie przy dodawaniu linii, a przy przekroczeniu 100 linii możemy sobie przealokować tablice, albo dorzucić kolejną i na niej operować.

// dodanie elementu do nowego wiersza
void push_back_row(Element* item) {
	Element** row = m_array + 4 * m_rows.size();
	row[0] = item;
	m_lines.push_back(row);
}

Przydałby się rysunek do zobrazowania tego, ale moje predyspozycje graficzne są nikłe :P

Póki, co jest to najlepsze rozwiązanie. W porównaniu do STL-owej wersji (vector w vectorze) przy 100 liniach po 4 elementy zaoszczędziliśmy 1200 bajtów (100 x sizeof(vector), w implementacji STL-a dołączanej w g++ 3.4.x rozmiar vectora wynosił 12 bajtów), czyli prawie 300 wskaźników, co odpowiada 75 nowym wierszom :P Nie rekompensuje to nawet tego, że w nie każdym wierszu musimy używać wszystkich 4 pozycji.

W sumie każdy powie, co to ~1.2KB przy dzisiejszych GB pamięciach :P Ale jakby każdy tak uważał, to czy niektóre systemy, czy programy działałyby tak jak działają, gdyby potrzebowały trochę więcej pamięci o 1 rząd więcej? Pewnie nie byłoby tak wesoło i niektórym nie podobałoby się to ;)

No tak, ale jak wielokrotnie wspominałem, mam małe zboczenie do optymalności i wydajności, ale lepsze to niż olanie lub założenie, że mamy nieskończoną ilość pamięci, czy zasobów :P

Wracając do tematu, wykorzystam rozwiązanie z jednowymiarową tablicą na dane, chyba ze znajdę lub wymyślę cos lepszego. Szkoda tylko ze przy operatorze [] na wierszu nie bedę miał sprawdzania zakresu, no chyba, że dla wersji debug opakuję ten wskaźnik do wiersza w jakąś prostą klasę z przeciążonym operatorem [] z assertem w środku ;) Do tego wypadałoby jeszcze napisać jakiś prosty iterator, który nie wiele musi mieć wspólnego z STL-owymi.

15/04/2008 @ 01:46

Po co się babrać różnymi tablicami jednowymiarowymi i problemami? W moim przypadku tablicy dwuwymiarowej najłatwiej będzie użyć zwykłej tablicy lub wektora i jedynie troszkę rozszerzyć jego szablon i ewentualnie iteratora. Nic więcej. Każde n-elementów tablicy będzie traktowane jako jeden wiersz. Jest to typowe i powszechne rozwiązanie problemu z prostymi tablicami dwuwymiarowymi. Dziwię się, że dopiero teraz na to wpadłem.

Wtedy można będzie używać różnych algorytmów STL-owych na tym kontenerze, kontenerze dzięki małym modyfikacjom, na elementach różnych kolumn etc, wierszowo na kolejnych elementach będzie zapewniał defaultowy iterator vectora.

Dla elementów o małych rozmiarach będzie to idealna tablica wielowymiarowa. Dla nieco większych nie będzie się zbytnio nadawać, bo wymagałoby to dużej jednolitej przestrzeni pamięciowej, aby uniknąć zabaw z różnymi blokami alokowanej pamięci miedzy wierszami.

Za kilka dni się tym pobawię i zobaczymy co wyjdzie ;)