On Tuesday, August 22, 2017 at 2:43:29 PM UTC+2, M.M. wrote:
> 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.


Nie. Przeczytaj raz jeszcze.
Opisałem, jakich struktur i algorytmów użyć aby zrealizować to,
co było w teście (dodać kupę elementów, potem zrobić kupę wyszukań)
szybciej niż za pomocą tego czasem spłaszczanego drzewa.


>
> > 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).


Dodanie masz w log, ale zaraz puszczasz sortowanie.
Więc efektywnie, w sytuacji, którą opisałeś
-modyfikacja drzewa,
-O(n) zapytań
-modyfikacja
...
modyfikacja zajmuje efektywnie tyle, co sortowanie.


> > 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.

Tak? Sortowanie co 6 ruchów nie odbije się na wydajności? ;-)


> > 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.

Masz opisane w poście.

Twój test wyglądał tak:

for (...)
insert(coś)

for (...)
delete(coś)

for (...)
find(coś)

Tworzysz dwa wektory, pierwszy V wypełniasz w pierwszej
pętli, drugi, Ve, w drugiej,
Sortuejsz oba, odpalasz na nich set_difference czy coś podobnego.
Wyniku używasz w trzeciej pętli.

Zbudowałeś specjalny test, w którym wychodza zalety Twojego
drzewa z sortowaniem. Ale do tego samego testu można zbudować
skuteczniejszą strukturę - zwykły wektor.


> > 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.


Ale ja nie odpowiadam w miejscu gdzie mówisz o uniwersalnej
wydajności, tylko tam, gdzie zaczynasz: "a jak się posortuje".


> > > 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.

Tak.



> > 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ą

Ale ja się z tym zgadzam i


> > 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).

Po wstawieniu chcesz znów korzystać z "szybszego" wyszukiwania.
Więc znów sortujesz.

pzdr
bartekltg