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.

do góry

W dniu 14.08.2017 o 15:47, Borneq pisze:
> czy trzy gałęzi długie rzędu 100 tys.
> Oto ciekawy problem.

Zapewne ma coś wspólnego z
https://pl.wikipedia.org/wiki/Rekurencja_ogonowa

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.

Ale pod jakim względem ciekawy? Żeby nie przekroczyć stosu przy
dużej ilości rekurencyjnych wywołań? Można zapamiętać wskaźniki w
tablicy liniowej, czyli w wektorze, a potem zwolnić pamięć na
podstawie wskaźników w tablicy.

Pozdrawiam

do góry

W dniu 14.08.2017 o 16:12, M.M. pisze:
> Ale pod jakim względem ciekawy? Żeby nie przekroczyć stosu przy
> dużej ilości rekurencyjnych wywołań? Można zapamiętać wskaźniki w
> tablicy liniowej, czyli w wektorze, a potem zwolnić pamięć na
> podstawie wskaźników w tablicy.

A czy samo przejście drzewa aby zapamiętać wskaźniki nie spowoduje
przekroczenie wysokości stosu?

do góry

W dniu 14.08.2017 o 16:44, Borneq pisze:
> A czy samo przejście drzewa aby zapamiętać wskaźniki nie spowoduje
> przekroczenie wysokości stosu?

Jak napisać rekurencję ogonową w C być może z użyciem goto?
Nie wiem czy w pełni ona załatwi, bo dobrze gdy rekurencja wołana jest
jako ostatnia w funkcji, a najdłuższa gałąź nie wiadomo która będzie.

do góry

On Monday, August 14, 2017 at 4:44:43 PM UTC+2, Borneq wrote:
> W dniu 14.08.2017 o 16:12, M.M. pisze:
> > Ale pod jakim względem ciekawy? Żeby nie przekroczyć stosu przy
> > dużej ilości rekurencyjnych wywołań? Można zapamiętać wskaźniki w
> > tablicy liniowej, czyli w wektorze, a potem zwolnić pamięć na
> > podstawie wskaźników w tablicy.
>
> A czy samo przejście drzewa aby zapamiętać wskaźniki nie spowoduje
> przekroczenie wysokości stosu?

Sprawdź w Twoim środowisku. Jak pamięci jest dużo, to można w
kompilatorze ustawić większy rozmiar - co zapewne wiesz.
Może coś bym podpowiedział, ale nie wiem w jakich okolicznościach
jest budowane takie drzewo, ani do czego jest potrzebne.

Pozdrawiam

do góry

On Monday, August 14, 2017 at 4:48:41 PM UTC+2, Borneq wrote:
> W dniu 14.08.2017 o 16:44, Borneq pisze:
> > A czy samo przejście drzewa aby zapamiętać wskaźniki nie spowoduje
> > przekroczenie wysokości stosu?
>
> Jak napisać rekurencję ogonową w C być może z użyciem goto?
> Nie wiem czy w pełni ona załatwi, bo dobrze gdy rekurencja wołana jest
> jako ostatnia w funkcji, a najdłuższa gałąź nie wiadomo która będzie.

Jak jest ciąg węzłów z jednym potomkiem, to zwalniaj w pętli, gdy
są dwa, to rekurencyjnie - może to wystarczy, nie wiem co dokładnie
robisz. 100tys na desktop/laptop to nie jest aż tak dużo.

do góry

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, nie wiem co dokładnie
> robisz. 100tys na desktop/laptop to nie jest aż tak dużo.

No włąśnie, teeen algorytm powinien mniej więcej tak wyglądać.
100 tys za dużo na stos, nawet 3 tysiące! przechodzi 2 tysiące

#include <stdint.h>
#include <random>

const int height = 2000;
uint8_t choos[height];

int active = 0;

struct Node
{
Node()
{
active++;
for (int i=0; i<3; i++)
children[i] = nullptr;
}
~Node()
{
for (int i = 0; i<3; i++)
if (children[i]) delete children[i];
active--;
}
Node *children[3];
};

int main()
{
std::mt19937 gen(0);
std::uniform_int_distribution<int16_t> dis(0, 2);
std::uniform_int_distribution<int16_t> dis2(1, 2);
std::uniform_int_distribution<int16_t> disoth(0, 5);
Node *node;
Node *child = new Node;
Node *head = child;
for (int i = 0; i < height; i++)
{
node = child;
choos[i] = dis(gen);
child = new Node;
node->children[choos[i]] = child;
if (dis(gen) == 0)
{
int second = (choos[i] + dis2(gen)) % 3;
node->children[second] = new Node;
}
}
delete head;
return 0;
}

do góry

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, ale jak to przedstawić w postaci kodu?
Może najpierw zamienić połowicznie - rekurencję na iterację z wektorem,
po czym ten wektor byłby używany tylko gdy rozgałęzienia?

do góry

W dniu 14.08.2017 o 17:15, Borneq pisze:
> 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, ale jak to przedstawić w postaci kodu?
> Może najpierw zamienić połowicznie - rekurencję na iterację z wektorem,
> po czym ten wektor byłby używany tylko gdy rozgałęzienia?
>
Robiłem coś takiego dla FloodFilla, ale tam za ramkę stosu wystarczał
jeden bajt kierunku (w rzeczywistości nawet bajt był za dużo) tutaj
trzeba by informację - może wskaźnik na obrabiane Node?

do góry