🚀 go-pugleaf

On Saturday, August 12, 2017 at 10:41:12 AM UTC+2, Wojciech Muła wrote:

> > Jak można to zrobić efektywniej? Trzeba zakodzić swoje drzewo czerwono
> > czarne? Jakbym zakodził swoje, to bym miał od razu na kiedyś statystyki 
> > pozycyjne...

> Wepnij własny alokator do std::map, niech on sobie trzyma liniową
> strukturę danych. I wtedy random robisz na tej strukturze.

Dziękuję za odpowiedź. To dobre rozwiązanie, chociaż nie mam 
doświadczenia z allocatorami, pewnie bym się namęczył zanim 
bym przebrnął przez to. Jeśli ktoś ma doświadczenie z 
allocatorami to zaproponowane przez Ciebie rozwiązanie chyba
jest optymalne pod względem nakładu pracy.

Po przemyśleniu doszedłem do ciut innego rozwiązania. Chciałem 
wyprowadzić klasę z QMap, a potem nadpisać wstawianie i usuwanie. 
W osobnej strukturze chciałem trzymać iteratory.

Potem jednak zastanowiłem się dalej i napisałem swoją wersję 
drzewa czerwono czarnego. Nie używam (jawnie) allocacji. Całość
oparłem o klasę QVector. Elementy drzewa nie mają wskaźników
do rodzica i potomków, lecz mają indeksy w QVector.

Uzyskałem w ten sposób szereg niezamierzonych i nieprzewidzianych
efektów. 

Po pierwsze, gdy program mało robi poza operacjami na drzewie, to 
działa od 1.5 do nawet 2 razy szybciej niż QMap i std::set. Mam
na myśli takie operacje jak wstawianie, przeszukiwanie z 
przodu do tyłu i z tylu do przodu, lower_bound, upper_bound, 
wyszukiwania i usuwania jeszcze nie sprawdzałem. Gdyby 
program tylko operował na drzewie, co jest niemożliwe, to pewnie
wersja na QVectorze działałąby 3 razy szybciej.

Drugi efekt, dane w qvector można posortować w czasie trochę
ponad liniowym względem ilości danych. Gdy jest dużo wyszukiwania,
to opłaca się posortować, a potem wyszukiwać binarnie na
wektorze. Wyszukiwanie na wektorze jest znacznie szybsze niż
na drzewie, może z 5 razy.

Kolejny efekt, mogę zwracać z drzewa referencje do danych nie-const.
Jeśli wiem że modyfikacja danych nie wpłynie na porządek w drzewie,
to nie muszę robić czasochłonnych:
remove
modify
insert

Dalej, gdy chodzi o QMap, to niestety ten szablon działa tylko dla
pary elementów, czyli trzeba zdefiniować pustą klasę Empty. Myslę, że
kompilatory całkowicie nie potrafią wywalić operacji na pustej klasie i
dodatkowo spowalniają cały kod.


Najdziwniejsze jest że moja wersja działa szybciej. Nie wiem dlaczego.
QMap nie jest thread-safety, std::set chyba też nie jest, więc żadnych
istotnych różnic w funkcjonalności nie widzę. Czyżby implementacja na
QVector dawała takie przyspieszenie?

Pozdrawiam