On Tuesday, August 22, 2017 at 4:15:30 PM UTC+2, M.M. wrote:
> 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 )

A dlaczego masz mieć dane dwa razy? Przecież każdy
obiekt istnieje tylko raz, nie robisz żadnych kopii*).
W maksymalnym momencie masz Ni+Ne, gdzie Ni to liczba
elementów dodanych w pierwszej iteracji, Ne w drugiej.

Jeśli Ni jest duże, np rzędu Ni, to rzeczywiście na raz trzymasz dwa
razy więcej elementów niż w przypadku drzewa, ale jeśli elementy
nie sa za duże, to i tak jesteś do przodu, to nie potrzebujesz
żadnych wskaźników.

*) set_difference robi kopię. Ale wersję która modyfikuje źródło
nie jest ciężko napisać.



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

Tylko raz, na poczatku, nie po każdej modyfikacji.
Wstawienie/usunięcie jednego elementu w posortowany ciag
jest O(n)

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

W tej części postu mówiliśmy o wersji "tablicowej",
gdzie drzewko posortowałeś. Więc tam modyfikacja
zajmuje O(sortowanie). Albo tracisz bonus od szybkiego
wyszukiwania i wtedy nie ma tematu.


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

Jaki, kurde, std::set?
std::set_difference to algorytm działajacy na dwóch posortowanych
zakresach (np wektorach).
Ale racja, trzeba go zmodyfikować, by działał w miejscu.


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



Wektor elementów do usunięcia nie rośnie, musisz go czyścić.
Jeśli w pierwszej petli skasowałeś '13', a potem w piątej dodałeś
13, to 13 ma być w kontenerze.

Liczac róznicę rób od razu odpowiednik unique.

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


Nie.
Jeśli bardzo chcesz, mozęmy wrócić do tematu (choc nie wiem,
do czego on daży, imho się trolociag zrobił), ale dopiero,
jak postarasz się zrozumieć, jaki algorytm i dlaczego
tam zapisałem.

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

Asymptotycznie to std::set daje to samo. myślałem, że
walczysz o stałą;-)


pzdr
bartekltg