On Tuesday, August 22, 2017 at 4:39:39 PM UTC+2, bartekltg wrote:
> 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.
Nawiązałeś do tamtego przykładu, a tam była jeszcze
pętla obejmująca to wszystko, więc pociągnąłem w tym
kierunku :) Ale masz rację, nie muszę mieć danych dwa
razy. Dla bezpieczeństwa muszę mieć strukturę o dobrych
właściwościach ogólnych, przykładem jest rb-tree. Okazało
się, że zaimplementowane rb-tree na tablicy działa i
szybciej w ogólnym przypadku, i umożliwia sztuczkę z
sortowaniem bez dodatkowej pamięci. Dlatego tak mocno
się przekonałem do takiej implementacji.


> 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ć.
Tak, można brać elementy z tyłu wektorów i wywoływać shrink_to_fit
co jakiś czas. Sztuczek jest wiele które w konkretnym przypadku
mogą przyspieszyć lub zaoszczędzić pamięć.

> Tylko raz, na poczatku, nie po każdej modyfikacji.
> Wstawienie/usunięcie jednego elementu w posortowany ciag
> jest O(n)
Rozumiem. Masz rację. Początkowo zrozumiałem, że w mojej
wersji drzewa wstawienie/usunięcie będzie kosztowało
O(N) po posortowaniu. Moim drzewie cały czas wstawienie i
usunięcie kosztują O(Log(N)).

Masz rację, że na początku można posortować dane. Sortowanie
prawdopodobnie będzie znacznie szybsze niż wstawianie do
drzewa. W dodatku, sortujemy same dane, a nie meta-dane
drzewa. Ja będę miał kopię, więc odtworzenie z kopii samych
danych będzie jeszcze szybsze. Algorytm:

for( j=0 ; j<M ; j++ )
set.insert( rand() );
for( j=0 ; j<K ; j++ ) {
set.insert( rand() );
for( k=0 ; k<L ; k++ )
set.search( rand() );
}

Dla L > M powinien zadziałać szybciej na posortowanej tablicy.

Jednak ten przykład podałem nie jako ostateczny cel, lecz
dlatego, aby upewnić się, że rozumiemy się co do liniowej
złożoności sortowania i logarytmicznej wyszukiwania, nawet
jeśli wyszukiwanie jest po sortowaniu i modyfikowaniu.

W praktyce czasami mogę mieć kilka insertów, albo L < M i
już na tablicy będzie ryzykownie.

Ja naprawdę chciałem uzyskać ogólną dobrą implementację, plus
to sortowanie jako jedno ulepszenie ekstra. Trochę boję się
stosować tablicy, bo po długim czasie programowania okaże się
że modyfikacji przypada więcej niż przewidziałem na początku i
będę musiał przerabiać.










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

Tak, bo zabrzmiałem zbyt dosłownie z tym przykładem w
którym wykonuję dokładnie jedną modyfikację :) To
był tylko przykład w celu który powyżej opisałem.
Masz rację, że gdy jest dosłownie jedna modyfikacja, to
na wektorze powinno działać szybciej.

Ale przynajmniej wiem dlaczego się nie rozumielismy :D

> 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.
Myślałem std::set_difference wypluwa std::set :) Nieważne. Ważne
że można to zaimplementować tak, aby 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.

Ale do usunięcia może napłynąć dużo takich samych liczb. Gdy usuwamy z
drzewa, to za pierwszym razem usuwamy, a potem próba usunięcia kończy
się niepowodzeniem. Gdy elementy do usunięcia kumulujemy w wektorze, to
wektor zawierający np. 4 różne liczby, może zawierać 40 liczb, czyli
może być 10krotny narzut pamięciowy. Przy usuwaniu z drzewa nie będzie
takiego narzutu. Tak samo dane do wstawienia mogą się skumulować w
wektorze, może być 10 razy dłuższy niż ilość różnych wartości.

> Liczac róznicę rób od razu odpowiednik unique.
Tak, ale zanim zrobię różnicę, to muszę tracić pamięć na kumulowanie
tych samych wartości. W drzewku nie ma tego problemu.

> 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.
Starałem się od początku, ale nie było to oczywiste, bo tamten
przykład podałem w innym celu i myślałem że z innego powodu
zarzucasz mi czas wstawiania O(N).

Nie ma problemu, mogę do bencznarków wrzucić i ten konkretny
przypadek z jednym insertem na N wyszukiwań. CHociaż bez
sprawdzania wiadomo na 99% że co do tego masz racje.


> Asymptotycznie to std::set daje to samo. myślałem, że
> walczysz o stałą;-)
A ja myślałem, że zarzucasz mi, że wstawianie mam gorsze
asymptotycznie, bo coś tam sortowanie psuje :D


Pozdrawiam