On Tue, 15 Aug 2017 12:25:59 -0700 (PDT), "M.M." <m...@g...com>
wrote:
> Nie wiem co będzie w C#. W Javie, gdy przypisze się root ==
> null, to
> prędzej czy później włączy się GC, wyczy=
> ści część lub wszystkie
> nody, potem odda sterowanie.

FYI

W C# jest tak samo.

do góry

On Tuesday, August 15, 2017 at 9:28:33 PM UTC+2, slawek wrote:
> On Tue, 15 Aug 2017 12:25:59 -0700 (PDT), "M.M." <m...@g...com>
> wrote:
> > Nie wiem co będzie w C#. W Javie, gdy przypisze się root ==
> > null, to
> > prędzej czy później włączy się GC, wyczy=
> > ści część lub wszystkie
> > nody, potem odda sterowanie.
>
> FYI
>
> W C# jest tak samo.

Czy w C++ mogą dać podobny efekt smart-pointery?
Pozdrawiam

do góry

On Monday, August 14, 2017 at 3:47:20 PM UTC+2, Borneq wrote:
> Nie patrząc już na shared_ptr i na listy,grafy cykliczne, mamy drzewko.
> Zwalniamy obiektowo tak że zwalniamy korzeń, wołany jest destructor dla
> korzenia, potem jego dzieci itd.
> Ale co gdy drzewo zdegeneruje się niemal do listy, tak że będziemy
> musieli rekurencyjnie zwalniać listę głębokości 100 tys i więcej?
> Samą listę można zwalniać iteracyjnie od korzenia lub końca. Ale co gdy
> zamiast listy mamy zdegenerowane głębokie drzewo, od którego co ileś
> odchodzą krótkie rozgałęzienia np. długości 20. Ewentualnie jest dwie
> czy trzy gałęzi długie rzędu 100 tys.
> Oto ciekawy problem.


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.

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

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

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.

pzdr
bartekltg


#include <iostream>
#include <vector>
#include <memory>
#include <algorithm>
#include <iterator>
using namespace std;

struct Node {
vector<unique_ptr<Node>> children;
int data;
Node(int x):data(x){}
~Node() { cout << "destruktor "<<data<<endl;}

};
class Tree {
unique_ptr<Node> root;
public:

~Tree(){
vector <unique_ptr<Node>> vec;
vec.push_back(move(root));
unsigned int i=0;

while (i<vec.size()) {
move(vec[i]->children.begin(),vec[i]->children.end()
, std::back_inserter(vec) );
cout<<"przenosiny dzieci "<<i<<": "<<vec[i]->data<<endl;
i++;
}
}
void push(int x){
if (root.get()==nullptr){
root = unique_ptr<Node>(new Node(x));
}else{
Node *n=root.get();
while( n->children.size()>0 )
n = (n->children[0].get());
n->children.push_back(unique_ptr<Node>(new Node(x)));
}

}

/*...*/
};



int main(int argc, char *argv[])
{
int c;

{
Tree tree;
for (int k=1000;k<1004;k++)
tree.push(k);
}

cout<<"bla"<<endl;

return 0;
}



OUT:
przenosiny dzieci 0: 1000
przenosiny dzieci 1: 1001
przenosiny dzieci 2: 1002
przenosiny dzieci 3: 1003
destruktor 1000
destruktor 1001
destruktor 1002
destruktor 1003

do góry

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

do góry

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

do góry

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

do góry

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

do góry

W dniu 16.08.2017 o 02:52, bartekltg pisze:
> unique_ptr<Node> root;
> while (i<vec.size()) {
> move(vec[i]->children.begin(),vec[i]->children.end()
, std::back_inserter(vec) );
> cout<<"przenosiny dzieci "<<i<<": "<<vec[i]->data<<endl;
> i++;
> }

a gdyby nie było unique_ptr? albo było shared_ptr?

do góry

W dniu 16.08.2017 o 02:52, bartekltg pisze:
> vector <unique_ptr<Node>> vec;

A ten wektor nie jest w całości na stosie?
czy lepiej vector <unique_ptr<Node>> *vec ?
czy też vector tylko podstawowe elementy ma na stosie a tablicę na stogu?
Jednak u mnie zdarzało się przepełnianie pamięci dużymi wektorami.

do góry

On Wednesday, August 16, 2017 at 3:46:41 PM UTC+2, Borneq wrote:
> W dniu 16.08.2017 o 02:52, bartekltg pisze:
> > unique_ptr<Node> root;
> > while (i<vec.size()) {
> > move(vec[i]->children.begin(),vec[i]->children.end()
, std::back_inserter(vec) );
> > cout<<"przenosiny dzieci "<<i<<": "<<vec[i]->data<<endl;
> > i++;
> > }
>
> a gdyby nie było unique_ptr? albo było shared_ptr?


"A gdyby nie słoń?"

Jakby zbudować drzewo inaczej, trzeba by zrobić jego kasowanie inaczej;-)
Jak, zależy od tego, jak to drzewo budujesz. Co robić na gołych wskaźnikach
masz w każdym podręczniku:)
Chocby robisz recznie rekurencyjnie: w procedurze usuwania usuwasz
dzieci, a potem to, na co wskazujesz. jest to odkładnie to, co automatycznie
robi unique_ptr, wiec ma ten sam "problem" ze stosem/

unique_ptr są o tyle lepsze, że kasowanie masz za darmo i ciezko
zrobić wyciek, a nie dają nakładu
Shared_ptr to liczenie referencji, do drzew niepotrzebnie i relatywnie
kosztowne.

pzdr
bartekltg

do góry