On Wednesday, August 16, 2017 at 12:24:19 PM UTC+2, bartekltg wrote:
> On Wednesday, August 16, 2017 at 12:08:07 PM UTC+2, M.M. wrote:
> > On Wednesday, August 16, 2017 at 11:40:04 AM UTC+2, bartekltg wrote:
> > > On Wednesday, August 16, 2017 at 11:21:12 AM UTC+2, M.M. wrote:
> > > > On Wednesday, August 16, 2017 at 2:52:19 AM UTC+2, bartekltg wrote:
> > > >
> > > > > Facet tu mówi o tym:
> > > > > https://www.youtube.com/watch?v=JfmTagWcqoE
> > > > > Ok 16 minuty zaczyna się właściwa cześć, wcześniej konstruuje
> > > > > drzewo na mądrych wskaźnikach.
> > > > > [...]
> > > >
> > > > Ja mam pytanie, w jakich zastosowaniach naprawdę jest potrzebne
> > > > drzewo na wskaźnikach (jakichkolwiek)? Ja mam drzewka zazwyczaj
> > > > na QVectorze, ale mogę też, jako odpowiednik allocatora, szablon
> > > > drzewka sparametryzować std::vector, std::array, itd.
> > >
> > > A co za różnica. Tu masz wskaźniki, u siebie masz indeksy.
> > > Na wskaźnikach jest ciut bardziej elastyczne jeśli chodzi
> > > o zwalnianie pamięci, ale masz pierdolnik z alokacją.
> > > Jeśli zrobisz pulę obiektów, to już w ogole różnicy nie będzie.
> > Poza tym
> > same zalety. Wszystkie operacje działają szybciej.
>
> Wszytkie operacje poza dodawaniem i usówaniem działąją
> tak samo szybko. Jak się postarać, to i dodawanie/usuwanie
> nie odbiega tak bardzo.

U mnie nie działają tak samo szybko. Zrobiłem testy na
wykrywanie błędów, póki co błędów nie znalazło, ale wiecie
jak to jest z oprogramowaniem... zawsze mogę robić coś źle.
Nie obiecuję że znajdę czas, ale postaram się wrzucić
gdzieś źródło z benchmarkami.

W skrócie: gdy porównuję moją, zrobioną zresztą na kolanie,
implementację drzewka czerwono-czarnego, to wszystkie
operacje na mojej implementacji działają wyraźnie
szybciej, względem QMap i std::set. Operacja clear działa
oczywiście milion razy szybciej.

> > Dużo
> > mniej pamięci potrzeba.
>
> Dlaczego "dużo"?
> @pula obiektów.
Opisywałem to chyba. Jeszcze raz. Są trzy powody:
1) Wskaźniki mają większy rozmiar niż typ uint32, uint16 i uint8, a
często takie typy wystarczą.
2) Malloc ma narzut (chyba) 16 bajtw na każdy węzeł.
3) Allokowany jest ciągły obszar pamięci, bez dziur, co jednak także
jest wadą, bo czasami w systemie nie ma dostępnego ciągłego długiego
obszaru.

> > Można zrobić prealokację.
> Tak, w obu wersjach można zrobić prealokacje.
Ok, ale w wersji wskaźnikowej to pociąga za sobą kolejną wadę:
musi być jeszcze wektor na wskaźniki, a taki wektor zajmuje pamięć.

> > Zwalnianie
> > pamięci całego(!) drzewa zajmuje mikrosekundy.
>
> Mało istotne.
> To samo możesz zrobić korzystając z puli.
Nie wiem czy zrozumiałem.. Jeśli się nie zwalnia, to pula żyje
przez całe życie programu, wtedy dla innych programów jest
mało pamięci, no i pula zrealizowana na wektorze też zajmuje
pamięć i zwalnianie na wektorze też pochłania czas. Nie wiem
czy to na pewno nie jest istotne. Jeśli mamy dużo małych
drzewek, to clear może być robione często, a program pobiera z
systemu tylko tyle pamięci, ile w danej chwili potrzebuje.


> > Gdy mamy
> > dużo wyszukiwań w stosunku do modyfikacji (w przypadku drzew
> > poszukiwań), to można wektor posortować i szukać binarnie w
> > wektorze - a to jest już o wiele szybciej.
>
> WTF.
> Jak potem chcesz odzyskać drewo?
Hmmm... o ile czegoś nie mylę, to drzewo cały czas jest poprawnym
drzewem czerwono-czarnym i nie trzeba czasu n*log(n) aby je
odbudowywać. Muszę się zastanowić nad tym porządnie.



> > W przypadku
> > gdy mamy wiele małych drzewek, to indeksy left, right, parent,
> > mogą być typami uint8 lub uint16, to jeszcze bardziej oszczędza
> > pamięć.
>
> Już omawialiśmy.
Omawialiśmy, ale nie wiem czy zmieniłeś zdanie, że to jednak oszczędza
pamięć.



> > Jakie są jeszcze zalety... można w czasie O(1) wyszukać
> > losowy element.
>
> Nieprawda. Jeśli usuwałes z drzewa, masz wektor wypełniony
> zyjącymi wierzchołkami i syfem.
Jakim syfem?


> Ok, możesz losować do skutku,
> dla niezbyt małego stopnia wypełnienia to nadal jest O(1),
> ale musizz dodać tam informację, czy wierzchołek żyje.
Chyba masz na myśli to, że w środku wektora robią sie dziury
po operacji remove/erase. W mojej implementacji nie robią
się dziury, bo od razu dziurę zastępuję ostatnim elementem i
oczywiście uaktualniam indeksy: left, right, parent. Od razu
odparuję zarzut: nie, takie usuwanie nie działa wolniej, póki co w
benchamarkach widzę, że działa szybciej, ale tak jak mówiłem,
porządne bęczmarki (może) dopiero wrzucę.





> > Może dla Was te zalety nie mają znaczenia, ale
> > dla mnie są bardzo ważne, niektóre programy dzięki temu mogę
> > uruchomić na komputerze z mniejszą pamięcią, inne działają np.
> > o 10-30% szybciej.
>
> To, że coś jest lepsze w jakimms szczegolnym przypadku
> nijak nie oznacza, że jest lepsze. A piszłes ogólnie.

Ogólnie dla mnie oznacza tyle samo co esperancja: prawdopodobieństwo
użycia razy czas wykonania. Jeśli operacje takie jak: wstawianie,
usuwanie, przeiterowanie od początku/tyłu, wyszukiwanie, upperBound,
lowerBound, clear, działają szybciej, w dodatku drzewko do 2mlnd
elementów zajmuje mniej pamięci, to esperancja będzie o wiele mniejsza.


> > Poza tym można ustawić wyrównanie. Poza tym malloc ma narzut,
> > którego na wek
>
> To nie używaj alokacji za każdym razem ;-)
To trzeba trzymać listę allokowanych elementów wraz z informacją
który został przydzielony i ta lista zabiera pamięć. I malloc
też będzie miało narzut, ale rację trzeba przyznać, że relatywnie
mniejszy.


> malloc? w c++? ;-)
New używa malloc.


> > > > W efekcie jest więcej trafień w
> > > > cache i drzewko jest w niektórych przypadkach 1.5 raza
> > > > szybsze.
> > >
> > > Tak, jak masz małe drzewo, to jest wiecej trafień.
> > Praktyka pokazuje, że gdy mam 1-10mln elementów w drzewie, to działa
> > dużo szybciej niż QMap i std::set.
>
> Mam jakieś wątpliwości do Twoich pomiarów, jeśli na dzień dobry
> porównujesz zupełnie różne kontenery;-)

Wątpliwości też jeszcze mam, bo to napisałem na kolanie, raz
zmierzyłem czas, tyle, że jak wrzuciłem do całego programu, to
działa przyzwoicie. Ale na pewno porównuję tę samą funkcjonalność.
A że inne kontenery, to pewnie, bo po co porównywać takie same?




>
> >
> > > > > Dośc pobieżnie, i jestem niemal pewien, ze kod, który pokazuje
> > > > > jest n^2 a nie nlogn ;-) Jeśli mamy wskaźnik na parent to łatwo
> > > > > naprawić.
> > > > >
> > > > > Pomysł, by zwalniać w pętli jeśli jest jeden potomek,
> > > > > rekurencyjnie, gdy więcej, nie sprawdzi się:
> > > > > /\
> > > > > /\
> > > > > /\
> > > > > /\
> > > > > /\
> > > > > /\
> > > > > /\
> > > > > /\
> > > > >
> > > > > To drzewo też ma głębokość O(n), a zwalniasz je rekurencyjnie.
> > > > > (do naprawienia, jeśli masz głęgokość poddrzewa, ale to bardzo
> > > > > szczegolny przypadek).
> > > >
> > > > Ale ostatni potomek też iteracyjnie.
> > >
> > > Nie rozumiem.
> > Gdy jest N dzieci w węźle, to po zwolnieniu N-1 dzieci, mamy tę samą
> > sytuację, jakby węzeł od początku miał jedno dziecko, więc możemy
> > potraktować to jako rekurencję ogonową.
>
> Pomyśl nad tym głębiej.
> Nie wiesz, która gałąź jest tą długą.
Ale jest jakieś niezerowe prawdopodobieństwo że tę dłuższą zwalnia się
na koniec, poza tym o tym pisałem przy założeniu, że wiadomo która
jest dłuższa.

Pozdrawiam