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.

Gdy robię benczmark, i gdy sumaryczny czas zwalniania z takich
struktur jak std::set, czy QMap trwa np. 10sekund, to w moim
nadal wynosi 0.000 - tak, stoper nie zdąży się włączyć.

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. W efekcie jest więcej trafień w
cache i drzewko jest w niektórych przypadkach 1.5 raza
szybsze.



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


> @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
węzły, drugi węzły których potomków jeszcze nie dodano do pierwszej -
tak można zamienić drzewko na wektor bez rekurencji. Gdy nie trzeba
zamieniać na tablicę, ale od razu zwalniać, to wystarczy wektor z
dziećmi których zwolniono rodziców.


> Przesuń usuwany wierzchołek do kontenera.
> Teraz całe drzewo tam siedzi, zaczepione pod ten element;-)
> Niech indeks pokazuje na ten (jedyny na razie) element. int i=0; :)
>
> Teraz w pętli:
> Wszystkie dzieci wierzchołka spod 'i' przerzuć do kontenera,
> i++
> Pętle konczysz, gdy i =size.
>
> Działająca przykąłdowa implementacja (wystarczy c++11, ale make_unique
> aż się  prosi gdziniegdzie:) poniżej.

Tak, chyba o tym samym myślałem.

Pozdrawiam