🚀 go-pugleaf

On Friday, August 11, 2017 at 4:29:38 PM UTC+2, M.M. wrote:
> Szukam efektywnej metody wybierania losowego elementu z takich
> struktur jak w tytule:
> 
> 1) QMap
> 2) std::set
> 
> Obie struktury mają to do siebie, że są zaimplementowane jako
> drzewa poszukiwań binarnych. Drzewka te maja mechanizm wyważania,
> zdaje się że są to drzewa czerwono czarne. Zatem struktury z bosta:
> 
> boost::container::flat_set
> 
> nie mogę użyć, bo wstawianie (o ile się nie mylę) jest w czasie O(N).
> 
> W QT ze struktury QMap próbowałem wybierać losowy element mniej/więcej w 
> taki sposób:
> 
> map.constBegin() + random() % map.size();
> 
> W std tak:
> 
> i = set.cbegin();
> std::advanced( i , random() % set.size() );
> 
> Obie metody w są koszmarnie wolne, zdaje się, że iterują po drzewku,
> czyli czas działania jest liniowy względem numeru elementu i jeszcze
> trochę zależy od głębokości drzewka.
> 
> 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.

w.

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