On Wednesday, August 16, 2017 at 4:07:30 PM UTC+2, M.M. wrote:
> 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ą

ała, usuwaniem. Biję się w klawiaturę.

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

Zauważyłeś warunek "poza dodawaniem/usuwaniem". Tu co najwyżej
rolę odegra lokalnośc, ale dla dużych drzew i tak masz same cache-miss.

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

A ja bym chcieł porównać to samo. Dla 256 max elementów sprawdziłbym
raczej boost flat_set.

> 2) Malloc ma narzut (chyba) 16 bajtw na każdy węzeł.

Dlatego pisałem o puli ;-)

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

I tu jest zaleta puli. Mogę alokowac po paczkach zadanych rozmiarów
(np najpierw rośnie *2, a potem ciągle 500MB). Moja pula jest ciut większym
obiektem, ale nigdy nie zaalokuje nic bardoz dużego.

Pamiętajmy też, że liczy się fragmentacja przestrzeni adresowej logicznej,
nie fizycznej. Nie wiem, co bym musiał robić, by sobie zdefragmentować
64bitowa przestrzeń adresową by nie móc wstawić tam paru GB:)

(pula nadal będzie alokowała kolejne fragmenty, a nie realokowała, bo
nie chemy przesówać tamtych obiektów)


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

Te obiekty już mają wskażniki. Trzymaj je jako listę ;-)

Raczej znów myślałem o puli.



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

Z puli nie będziesz zwalniał w momencie usuwania z drzewka,
przynajmniej nie w oczywisty sposób (chyba, że zgodzisz się
na to, że erase unieważnia iteratory - przestawia fizycznie
elementy).
Ale:
-jeśli drzewko jest ciągle używane, to usuniete elementy
są uzywane ponownie, więc struktura zajmuje tyle pamięci, ile
zajęła w szczytowym momencie (+trochę, w końcu vector potrafi
zająć 2*wiecej niż ma elementów).
-Jeśli robisz clear drzewku często, to jest to sytuacja idealna.
Clear na puli, root = nullptr i jest posprzątane.
W wersji jedna pula na jedno drzewko. Alternatywnym podejsciem jesty
pula na wszytkie małe drzewka, ale wtedy znów, co prawda pamięć pomiędzy
drzewkami przekłada się ładnie, ale znów trzeba się namęczyć ze zmniejszaniem
pamięci (w tym unieważnione zostaną wskażniki)

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

Masz drzewko rb, skłąda się ono z nodów, w których jest:
dane, bit o kolorze, wskaźniki do dzieci. I wszytkie nody możesz
trzymać w vector.
Jak sobie posortujesz po 'dane' to te wskaźniki pokakzują
w losowe miejsca.

No, chyba, że z tym drzewem rb to mydliłęś oczy i tak naprawdę masz
coś w rodzajju kopca/drzewa binarnego pełnego, gdzie dzieci 'i' są
na wspolrzednych 2i i 2i+1 ;-)


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

Nie zmieniłem zdania, że jest to niszowa optymalizacja dla bardzo
konkretnego zastosowania;-)

>
>
>



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

Ok. No to zrobiłeś dokładnie to, co ja nazywałem pulą;-)
tylko prościej zaimplementowaną, bo nie przejmujesz się tym,
by kontener miał iteratory.
Od strony wydajnościowej (dla indeksów rozmiaru wskaźników)
wydajność jest ta sama.



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


Tablica bitów zajmuje 1/8 bajta na obiekt. Malloc trzyma size_t,
a być moze i wiecej, a do tego wyrównuje do 16.
To zawsze jest lepiej:)

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

To może tez pisz winapi::HeapAlloc ;-)

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

A ja wprost napisałęm, że tego nie wiemy;>
"(do naprawienia, jeśli masz głęgokość poddrzewa, ale to bardzo
szczegolny przypadek). "

pzdr
bartekltg