Zalety i wady implementacji drzew czerwono czarnych na tablicy

Opisywana implemetnacja drzew czerwono-czarnych na tej stronie została zrealizowana w oparciu o ciągły obszar pamięci, innymi słowy, w oparciu o tablicę elementów. Taki obszar pamięci można zapewnić przy pomocy odpowiedniego allocatora. Przykładowymi allocatorami mogą być: struktura QVector z biblioteki QT, std::vector z biblioteki standardowych szablonów w C++, a nawet std::array i QVarLengthArray. Można też samodzielnie obudować zwykłą tablicę klasą C++ i przekazać tę klasę jako parametr szablonu RBTree. Dla wygody zostały przygotowane trzy gotowe allocatory.
Zatem już na pierwszy rzut oka widać, że ta implementacja drzew czerwono czarnych nie jest standardowa, ponieważ zwykle spotykamy się w praktyce i w literaturze z implementacją na wskaźnikach. Z implemetnacją na ciągłym obszarze pamięci wiąże się szereg zalet i wad.

Zalety implementacji na tablicy

  1. W pobieżnych testach implementacja na tablicy działa szybciej.
  2. Rzadziej jest wywoływana funkcja malloc, jest mniejszy narzut pamięciowy.
  3. Można wykorzystać wersję z polami bitowymi i zaoszczędzić jeszcze więcej pamięci.
  4. Gdy przetrzymujemy dużą ilość małych drzew, to możemy do indeksowania użyć typu int8 lub int16, a to w kolejny sposób zaoszczędzi pamięć.
  5. Zwalnianie pamięci sprowadza się tylko do jednego wywołania free, działa bardzo szybko.
  6. Można elementy drzewa posortować w czasie zaledwie liniowym O(N) i potem zastosować wersje funkcji z przedrostkiem sort. Funkcje z przedrostkiem sort działają wielokrotnie szybciej.
  7. W trakcie sortowania, bez zwiększania czasu O(N), można zbudować strukturę hash-table i jeszcze bardziej przyspieszyć wyszukiwanie. Ta cecha w chwili pisania tego tekstu, nie jest jeszcze zaimplementowana. Niestety funkcje takie jak lowerBoudn i upperBound nie mogą wykorzystać hash-table.
  8. Gdy dane mają równomierny rozkład to można zastosować wyszukiwanie interpolacyjne - ta cecha również nie jest jeszcze zaimplementowana.
  9. Klasa RBTree zwraca referencje do elementów nie-const. Jeśli programista wie, że modyfikacja elementu nie wpłynie na porządek w drzewie, to może element zmodyfikować bez konieczności jego usuwania i ponownego wstawiania - ale to już jest zaleta tej konkretnej implementacji względem std::set i QMap, a nie zaleta wynikła z implementacji na tablicy.

Wady implementacji na tablicy

  1. W trakcie dodawania elementów wektor zwiększa swój rozmiar. Czasami wymaga to przekopiowania elementów wcześniej dodanych, co skutkuje tym, że czasami dodawanie jednego elementu trwa bardzo długo. Jednak czas zamortyzowany w testach był krótszy niż w std::set i QMap.
  2. W trakcie dodawania elementów tablica zwieksza swój rozmiar o dużą ilość pamięci. Może być konieczne dopasowanie pamięci do ilości faktycznie przechowywanych elementów w wektorze (metody typu squeeze, shrink_to_fit).
  3. Trzeba użyć typu int64 i przystosowanej tablicy do tego typu, gdy chcemy przechowywać w drzewie więcej niż 2mld elementów.
  4. Po operacji usuwania indeksy mogą stracić ważność. Jeśli w Twojej aplikacji zachodzi konieczność: przechowywania indeksów  i usuwania/modyfikowania elementów z drzewa, to tablicowa implementacja drzew czerwono czarnych nie jest odpowiednia dla Twojej aplikacji. Będę wdzięczny za podanie przykładów takich aplikacji.
  5. W celu optymalizacji używanie tej implementacji minimalnie mniej wygodne niż np. std::set i QMap, jednak jest to już tylko wada tej konkretnej implementacji, a nie w ogóle implementacji na tablicy i wynika z niej zaleta: minimalnie większa wydajność.
 Moim zdaniem zalety znacznie przewyższają wady, ale każdy niech oceni sam.

Komentarze

Popularne posty z tego bloga

benchmark 00 tablicowej implementacji drzew czerwono czarnych

metodyka testowania implementacji drzew czerwono czarnych na bazie tablicy