On Monday, August 14, 2017 at 5:15:23 PM UTC+2, Borneq wrote:
> W dniu 14.08.2017 o 16:50, M.M. pisze:
> > Jak jest ciąg węzłów z jednym potomkiem, to zwalniaj w pętli, gdy
> > są dwa, to rekurencyjnie - może to wystarczy,
>
> To całkiem dobre rozwiązanie,
Na długich zdegenerowanych odcinkach nie robi rekurencyjnego wywołania,
może to wystarczy do Twojego zastosowania.

> ale jak to przedstawić w postaci kodu?

Bez debugowania tak:
remove( node ) {
while( node ) {
if( node->childCount() > 1 ) {
foreach( node->childs as child ) {
remove( child )
}
delete node
} else {
tmp = node;
node = node->chils[ numberOneChild ];
delete node;
}
}
}

> Może najpierw zamienić połowicznie - rekurencję na iterację z wektorem,
> po czym ten wektor byłby używany tylko gdy rozgałęzienia?
Nie wiem, pewnie skomplikowałoby mocno kod. Ja mam po prostu
wszystko w wektorze, robię clear i cała pamięć zwolniona.

Pozdrawiam

do góry

W dniu 14.08.2017 o 17:50, M.M. pisze:
> Bez debugowania tak:
> remove( node ) {
> while( node ) {


Poprawiona metoda działa, ale zagłębia się za bardzo, bo często
childCount > 1, tyle że inne gałęzie są krótkie a jedna czy kilka długie.

void remove(Node *node)
{
while (true) {
int childCount = 0;
int numberOneChild = -1;
for (int i = 0; i < 3; i++)
{
if (node->children[i])
{
childCount++;
numberOneChild = i;
}
}

if (childCount > 1)
{
for (int i = 0; i < 3; i++)
if (node->children[i])
{
tuheight++;
remove(node->children[i]);
tuheight--;
}
delete node;
return; //<--- z debugowania wychodzi tu return
}
else if (childCount == 1)
{
Node *tmp = node;
node = node->children[numberOneChild];
delete tmp;
}
else
{
delete node;
return;
}
}
}

do góry

On Monday, August 14, 2017 at 6:56:58 PM UTC+2, Borneq wrote:
> W dniu 14.08.2017 o 17:50, M.M. pisze:
> > Bez debugowania tak:
> > remove( node ) {
> > while( node ) {
>
>
> Poprawiona metoda działa, ale zagłębia się za bardzo, bo często
> childCount > 1, tyle że inne gałęzie są krótkie a jedna czy kilka długie.

Hmmm, nie wiem co dla Ciebie znaczy "bardzo". Dwadzieścia zagłębień, przy
breanch-factor 2.5, oznacza, że drzewko ma np. 90mln węzłów. Kiedyś
chyba też miałem styczność z takim mocno zdegenerowanym drzewie...
niestety szczegółów już nie mogę sobie przypomnieć. Wydaje się, że
ta procedura nie zagłębi się powyżej 40 wywołań, może jeszcze jakiś
błąd jest w kodzie?

Pozdrawiam

do góry

W dniu 14.08.2017 o 20:04, M.M. pisze:
> Hmmm, nie wiem co dla Ciebie znaczy "bardzo". Dwadzieścia zagłębień, przy
> breanch-factor 2.5, oznacza, że drzewko ma np. 90mln węzłów. Kiedyś
> chyba też miałem styczność z takim mocno zdegenerowanym drzewie...
> niestety szczegółów już nie mogę sobie przypomnieć. Wydaje się, że
> ta procedura nie zagłębi się powyżej 40 wywołań, może jeszcze jakiś
> błąd jest w kodzie?

Chodzi o bardziej zdegenerowane, przypominające listy. Ale ta metoda
może być. Dla 10 tys moja przerobiona na iterację ma 10 tys zagłębienia,
a dla tego przykładu z Twoją optymalizacją 1/3 tego.
https://gist.github.com/borneq/a1f5d7a45b08c77414a44
4462547d8a1

do góry

On Monday, August 14, 2017 at 11:44:06 PM UTC+2, Borneq wrote:
> W dniu 14.08.2017 o 20:04, M.M. pisze:
> > Hmmm, nie wiem co dla Ciebie znaczy "bardzo". Dwadzieścia zagłębień, przy
> > breanch-factor 2.5, oznacza, że drzewko ma np. 90mln węzłów. Kiedyś
> > chyba też miałem styczność z takim mocno zdegenerowanym drzewie...
> > niestety szczegółów już nie mogę sobie przypomnieć. Wydaje się, że
> > ta procedura nie zagłębi się powyżej 40 wywołań, może jeszcze jakiś
> > błąd jest w kodzie?
>
> Chodzi o bardziej zdegenerowane, przypominające listy. Ale ta metoda
> może być. Dla 10 tys moja przerobiona na iterację ma 10 tys zagłębienia,
> a dla tego przykładu z Twoją optymalizacją 1/3 tego.
> https://gist.github.com/borneq/a1f5d7a45b08c77414a44
4462547d8a1

Ok. Nie wszystko rozumiem, ale to nieważne, ważne, że "może być" :)
Pozdrawiam

do góry

On Monday, August 14, 2017 at 11:44:06 PM UTC+2, Borneq wrote:
> W dniu 14.08.2017 o 20:04, M.M. pisze:
> > Hmmm, nie wiem co dla Ciebie znaczy "bardzo". Dwadzieścia zagłębień, przy
> > breanch-factor 2.5, oznacza, że drzewko ma np. 90mln węzłów. Kiedyś
> > chyba też miałem styczność z takim mocno zdegenerowanym drzewie...
> > niestety szczegółów już nie mogę sobie przypomnieć. Wydaje się, że
> > ta procedura nie zagłębi się powyżej 40 wywołań, może jeszcze jakiś
> > błąd jest w kodzie?
>
> Chodzi o bardziej zdegenerowane, przypominające listy. Ale ta metoda
> może być. Dla 10 tys moja przerobiona na iterację ma 10 tys zagłębienia,
> a dla tego przykładu z Twoją optymalizacją 1/3 tego.
> https://gist.github.com/borneq/a1f5d7a45b08c77414a44
4462547d8a1

Nie wiem jak budujesz to drzewko, ale są możliwe jeszcze dwie
optymalizacje. Trzeba w węźle zapamiętać maksymalną głębokość
wszystkich pod-gałęzi. Czyli depth(rodzic) = max( depth(childs) ) + 1.
Potem można:
1) najpierw wchodzić do najpłytszych pod-gałęzi
2) ostatniego potomka można iteracyjnie zwalniać.

Pozdrawiam

do góry

W dniu 15.08.2017 o 03:33, M.M. pisze:
> wszystkich pod-gałęzi. Czyli depth(rodzic) = max( depth(childs) ) + 1.
> Potem można:
> 1) najpierw wchodzić do najpłytszych pod-gałęzi
> 2) ostatniego potomka można iteracyjnie zwalniać.

W tym moim teoretycznym przykładzie nie da się rozstrzygnąć które jest
najgłębsze, bo jest 3 potomków wybieranych losowo. Może w innym
przykładzie dało by się to określić, bo okazało by się że zawsze
najgłębsza gałąź związana jest z potomkiem numer 2.

do góry

On Tue, 15 Aug 2017 07:59:17 +0200, Borneq
<b...@a...hidden.pl> wrote:
> W tym moim teoretycznym przykładzie

A co się stanie gdy w C# ręcznie zwolni się korzeń i nic więcej?

To chyba wiem za co lubię C#.

do góry

W dniu 15.08.2017 o 11:58, slawek pisze:
> A co się stanie gdy w C# ręcznie zwolni się korzeń i nic więcej?
> To chyba wiem za co lubię C#.

Zainteresowałem się językami bez Garbage Collectora. Rust wymaga by był
tylko jeden właściciel na raz, ale trudno spełnić te wymogi. Swift liczy
referencje, czy Swift to idealny język?

do góry

On Tuesday, August 15, 2017 at 11:58:07 AM UTC+2, slawek wrote:
> On Tue, 15 Aug 2017 07:59:17 +0200, Borneq
> <b...@a...hidden.pl> wrote:
> > W tym moim teoretycznym przykładzie
>
> A co się stanie gdy w C# ręcznie zwolni się korzeń i nic więcej?
>
> To chyba wiem za co lubię C#.

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.

Pozdrawiam

do góry