On Tuesday, August 22, 2017 at 3:34:37 PM UTC+2, bartekltg wrote:
> 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.

Czytałem, zrozumiałem tak. Dodajesz do drzewa N (N>1mln)
elementów. Czas dodawania O( N * Log(N) ). Ilość pamięci
N * (dane + narzut węzła wskaźnikowego + narzut allocatora). Potem
tworzysz posortowany wektor. Czas wyniesie O(N). Zajęta
dodatkowa pamięć N * dane. Potem wyszukujesz M (M dużo
większe od N) razy na wektorze. Czas M * Log(N). Potem
można zwolnić wektor i znowu modyfikować dane w drzewie w
czasie Log(N).

Łączny czas: O( N * Log(N)) + O(N) + M * Log(N).
Łączna pamięć: N * (2 * dane + narzut węzła wskaźnikowego + narzut allocatora)

U mnie to samo zajmuje (asymptotycznie) tyle samo czasu, ale
znacznie mniej pamięci: N * (dane + narzut węzła indeksowego )






> 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.
Nie rozumiem. W Twoim rozwiązaniu też jest sortowanie.

W moim drzewku czasy wyglądają tak (w tej kolejności):
1) wstawianie N elementów: O(N*Log(N))
2) sortowanie drzewa: O(N):
3) wyszukanie M razy: M * Log(N)
4) wstawianie K elementów O( K * Log(N+K) )

Jest identycznie, tylko implementacja szybsza i mniej pamięci
zajmuje.





> > > 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? ;-)
Ale w mojej wersji nie trzeba sortować i bez sortowania
działa wiele szybciej niż std::set. Sortowanie to tylko
ekstra możliwość na wypadek długiego ciągu wyszukiwania.



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

Ok, ale przez moment w pamięci są dwa niepotrzebne wektory i potrzebny
std::set. To jest to samo, tylko jest wolniejsza implementacja i
więcej pamięci zajmuje.


> 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.
Nie sądzę. Zwróć uwagę, że te trzy operacje są zapętlone. Po
serii find, jest znowu seria insert i remove. TO jest raczej
coś takiego:

for( ... ) {
for (...)
insert(coś)

for (...)
delete(coś)

for (...)
find(coś)
}

Wektor insertów rozrośnie się niepotrzebnie, gdy będą wstawiane
te same elementy. Wektor elementów do usuniecia też niepotrzebnie
się rozrośnie w przypadku powtórzeń i w przypadku elementów których
nie ma w insertach.


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

Gdy jest dużo wyszukiwania, Ty proponujesz zrzut danych do
osobnego wektora. Ja sortuję w tej samej pamięci w której
są węzły drzewa. Moje rozwiązanie jest lepsze o to, że
nie potrzeba dodatkowej pamięci. Poza tym asymptotycznych
różnic nie ma. Moja implementacja z tego co na razie
widzę, jest dużo szybsza, ale np. set_difference jeszcze
nie sprawdzałem.

> Po wstawieniu chcesz znów korzystać z "szybszego" wyszukiwania.
> Więc znów sortujesz.
Sortuję tylko gdy zapowiada się długi ciąg wyszukiwania w
porównaniu do ilości elementów w drzewie. Gdy np.:

ilość węzłów * 1.5 < ilość wyszukiwań

Może się opłacać nawet gdy:
ilość węzłów * 1.1 < ilość wyszukiwań

I tak samo można postępować na zewnętrznym wektorze, w
rozwiązaniu w które Ty zaproponowałeś.

Gdy ilość wyszukiwań jest relatywnie mała, to wyszukuję bez
uprzedniego sortowania i mam wydajność w mojej implementacji
około 1.5 - 3.0 raza szybszą niż std::set.



Pozdrawiam