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.

Są różnice. Wada jest taka, że potrzebny jest duży i ciągły
obszar pamięci. W przypadku bardzo dużych drzewek może
być to problem. Gdy chcemy mieć powyżej 2^32 węzłów, to na
uint32 też nie zrobimy tego. Jeszcze jedna jest wada, po
usunięciu węzła, indeksy mogą się zdeakutalizować. Poza tym
same zalety. Wszystkie operacje działają szybciej. Dużo
mniej pamięci potrzeba. Można zrobić prealokację. Zwalnianie
pamięci całego(!) drzewa zajmuje mikrosekundy. 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. 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ęć. Jakie są jeszcze zalety... można w czasie O(1) wyszukać
losowy element. 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.


> > Drzewko na tablicy jest niby ciut wolniejsze, ale oszczędza
> > pamięć, bo jako indeksy można użyć int8, int16, int32, a
> > wskaźnik ma rozmiar 64 bity.
>
> Można, jeśli masz małe drzewo.
> Wyrównanie i tak pewnie kopnie w tyłek i będize to samo co int32.
Nie, bo są trzy indeksy: left, right i parent, zakumulują się.
Poza tym można ustawić wyrównanie. Poza tym malloc ma narzut,
którego na wek

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


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


> > > @pomysł M.M. by przerzucić wierzchołki do innego kontenera i tam je
> > > skasować (pomysł wspominany i w filmiku) nie wymaga tak dużego stosu.
> > To chyba najprostsza metoda. Dwa wektory są potrzebne. Jeden ma
>
> Nie. Jeden vector wystarczy. Rozwi,ązanie miałeś niżej.
Do samego zwolnienia wystarczy jeden, wspomniałem o tym poniżej.

Pozdrawiam