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.

> Dużo
> mniej pamięci potrzeba.

Dlaczego "dużo"?
@pula obiektów.

> Można zrobić prealokację.
Tak, w obu wersjach można zrobić prealokacje.


> Zwalnianie
> pamięci całego(!) drzewa zajmuje mikrosekundy.

Mało istotne.
To samo możesz zrobić korzystając z puli.

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


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

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

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


> 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 ;-)
malloc? w c++? ;-)


> > > 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;-)

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

Pozdrawiam