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.


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

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


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

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

pzdr
bartekltg