On Tuesday, August 22, 2017 at 12:23:00 PM UTC+2, bartekltg wrote:
> I jest jeszcze to, że RB mają mniejszy rozrzut czasów.
> Nieraz też to jest istotne.
Tak, to prawda, choć rzadka sytuacja, np. gdy urządzenie ma limit
czasu oczekiwania na odpowiedź.


> Jeśli mam serię wstaweń (i ewentialnie usuwań) a potem wyszukiwania
> to wstawiam w nieposortowany vector, potem go sortuję (jeśli coś
> usuwam to do osobnej listy, sortuję, a potem std::set_difference)
> i teraz wyszukuję na posortowanym wektorze.
Ale chyba teraz piszesz o metodzie zaproponowanej przeze mnie, tyle
że wolniej działającej i zajmującej więcej pamięci. Gdy rb-tree
jest zaimplementowane na tablicy, to nie trzeba osobnego wektora, a
samo rb-tree zajmuje mniej ramu.


> Wstawianie mam liniowo (i znacznie szybciej niż Ty), sortowanie
> też nieco szybciej.
Nie rozumiem. Ja mam wstawianie w O(Log(N)) < O(N). Sortowanie
mam w O(N).


> Jeśli mówię, że drzewo będzie używane z przewagę wstawień/usunieć,
> albo wyszukiwań, to znaczy, że np 5 jednych będzie przeplatane tym drugim,
> nie, że wystąpią one po kolei.
Tak zrozumiałem, ale dla benchamrku na jedno wychodzi.



> Uporządkowanie tych działań to bardzo spacyficzne zastosowanie,
> i, jak widać powyzej, da sie je zrobić nawet szybciej.
Może coś ze mną nie tak, nie widzę na razie nic szybszego.


> A tu dyskutujemy o uniwersalnych drzewkach.
W różnorodnym teście moja implementacja też działa szybciej niż
std::set i QMap. Specjalnie na potrzeby naszej rozmowy napisałem
drzewko tak, aby było uniwersalne. Nie wiem o co chodzi.



> > Oczywiście jest jeszcze i taka możliwość, że w losowej chwili
> > robimy jedną modyfikację na 5-30 wyszukiwań. Gdy jest to 5, to
> > może lepsze będą rb-tree, gdy 30, to może AA-tree. Trudno
> > powiedzieć bez zmierzenia.
> >
> > Chwilowo mam taką sytuację w której mogę przewidzieć, że po jednej
> > modyfikacji będą miliony wywołań lowerBound, więc rb-tree na tablicy z
> > sortowaniem wydaje się najlepsze.
>
> Jeśli masz miliardy elementów - niekoniecznie;-)
Miliardy w sensie, że więcej elementów w drzewie niż wyszukiwań? Tak, wtedy
się nie opłaca sortować nawet w czasie liniowym. Miliardy w sensie, że
trzy miliardy już się nie zmieszczą w int32 i trzeba indeksować tablicę
typem int64... nie wiem ile to spowolni, nie sprawdzałem.


> A jeśli Ci się opłaca sortować po wstawieniu jednego elementu,
> to tym bardziej opłaca Ci się... wstawić liniowo element do posortowanego
> ciagu.
Tak. Ale wtedy bym musiał w jednym algorytmie zastosować kilka
wyspecjalizowanych struktur. A tak mam JEDNĄ strukturę uniwersalną
(drzewo rb-tree), zaimplementowaną na tablicy, czyli już
szybszą ze dwa razy niż std::set bez żadnych sortowań. A gdy
przewiduję duży ciąg wyszukiwania, to mogę zrobić sort
przed tym ciągiem i uzyskać przyspieszenie z 3-4 razy, może
nawet 5. Po sortowaniu i wyszukiwaniu drzewo działa jak uniwersalne
rb-tree, nic nie trzeba naprawiać, nic nie trzeba odzyskiwać, można
od razu robić remove i insert. Dzięki temu mam JEDNĄ strukturę która
zarazem może pomieścić 50tys elementów (posortowanie tego w
wektorze to około 1.25mld samych porównań, a gdzie przestawianie
danych), z której niskim kosztem obliczeniowym i pamięciowym mogę
zrobić posortowany wektor.

Pewnie że lepiej byłoby mieć pięć wyspecjalizowanych struktur, a
algorytm byłby nadal elegancki, bo można to załatwić metodą wirtualną.

Jedna struktura to drzewko z sortowaniem w miejscu - takie jakie
zrobiłem. Potem dwie odmiany: z wyszukiwaniem binarnym i interpolacyjnym.
To by miało sens gdzieś od 150 elementów w górę.

Druga struktura to uporządkowany wektor z wyszukiwaniem binarnym lub
interpolacyjnym. To by miało sens gdzieś od 30 elementów w górę.

W końcu wektor nieuporządkowany, to by mogło do około 30 elementów
działać najlepiej.

Można też zrobić tak, że gdy zbiór przekroczy N elementów, to przechodzi
automatycznie na lepszą asymptotycznie strukturę, gdy przekroczy M, to
na kolejną lepszą, a po remove wraca na strukturę gorszą. ALe to jest
już jakość na którą chwilo nie mogę sobie pozwolić. Myślę, że drzewko z
na tablicy jest bardzo dobrą implementacją, a z sortowaniem jest
optymalne gdy spodziewamy się długiej serii wyszukiwania.


> Chyba dokładnie to robi flat_set z boosta. Wyszukujesz właściwe miejsce,
> wstawiasz tam nowy element, a wszytkie kolejne przesuwasz o oczko w prawo.
Tak. Nie wiem jakie ma bebechy. Można taką strukturę zrobić i z pewnym
procentem dziur, zwiększy się czas wyszukiwania, zmniejszy czas wstawiania,
ale dziury można usunąć, jeśli się przewiduje długą serię wyszukiwań, a
potem można dziury wstawić przed serią wstawień.

> Wstawienie jest O(n), ale szybkie (tylko raz dotykasz pamieci, i to średnio
> tylko połowy),
Tak, tutaj się zgadzam całkowicie. Jedno wstawianie jest w czasie O(N).


> w porównaniu do Twojego, gdzie efektywnie masz wstawienie
> o koszcie O(n log n).
Nie wiem dlaczego tak myślisz, coś źle wytłumaczyłem, czy pomyliłeś
się po prostu? Może ja czegoś nie rozumiem? Mam, nawet po posortowaniu,
wstawianie, usuwanie i modyfiakcję w czasie O(Log(N)) < O(N).


> > Wrzuciłem na bloga ulepszony program do przetestowania:
> > https://drzewa-czerwono-czarne.blogspot.ch/p/kod-zro
dowy-programu-testujacego.html
>
> Widziałem, nadal nie mam kiedy czytac.
Ok.

Pozdrawiam