Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #30223 > unrolled thread

Ciekawy problem iteracyjnego zwalniania głębokiego drzewa

Back to article view | Back to pl.comp.programming

Contents

  Ciekawy problem iteracyjnego zwalniania głębokiego drzewa Borneq <borneq@antyspam.hidden.pl> - 2017-08-14 15:47 +0200
    Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa Borneq <borneq@antyspam.hidden.pl> - 2017-08-14 15:53 +0200
    Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa "M.M." <mmarszik@gmail.com> - 2017-08-14 07:12 -0700
      Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa Borneq <borneq@antyspam.hidden.pl> - 2017-08-14 16:44 +0200
        Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa Borneq <borneq@antyspam.hidden.pl> - 2017-08-14 16:48 +0200
          Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa "M.M." <mmarszik@gmail.com> - 2017-08-14 07:50 -0700
            Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa Borneq <borneq@antyspam.hidden.pl> - 2017-08-14 17:11 +0200
            Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa Borneq <borneq@antyspam.hidden.pl> - 2017-08-14 17:15 +0200
              Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa Borneq <borneq@antyspam.hidden.pl> - 2017-08-14 17:20 +0200
              Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa "M.M." <mmarszik@gmail.com> - 2017-08-14 08:50 -0700
                Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa Borneq <borneq@antyspam.hidden.pl> - 2017-08-14 18:56 +0200
                  Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa "M.M." <mmarszik@gmail.com> - 2017-08-14 11:04 -0700
                    Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa Borneq <borneq@antyspam.hidden.pl> - 2017-08-14 23:44 +0200
                      Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa "M.M." <mmarszik@gmail.com> - 2017-08-14 15:20 -0700
                      Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa "M.M." <mmarszik@gmail.com> - 2017-08-14 18:33 -0700
                        Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa Borneq <borneq@antyspam.hidden.pl> - 2017-08-15 07:59 +0200
                          Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa slawek <fake@fakeemail.com> - 2017-08-15 11:58 +0200
                            Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa Borneq <borneq@antyspam.hidden.pl> - 2017-08-15 12:55 +0200
                            Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa "M.M." <mmarszik@gmail.com> - 2017-08-15 12:25 -0700
                              Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa slawek <fake@fakeemail.com> - 2017-08-15 21:27 +0200
                                Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa "M.M." <mmarszik@gmail.com> - 2017-08-15 15:20 -0700
        Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa "M.M." <mmarszik@gmail.com> - 2017-08-14 07:49 -0700
    Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa bartekltg <bartekltg@gmail.com> - 2017-08-15 17:52 -0700
      Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa "M.M." <mmarszik@gmail.com> - 2017-08-16 02:21 -0700
        Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa bartekltg <bartekltg@gmail.com> - 2017-08-16 02:40 -0700
          Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa "M.M." <mmarszik@gmail.com> - 2017-08-16 03:08 -0700
            Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa bartekltg <bartekltg@gmail.com> - 2017-08-16 03:24 -0700
              Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa "M.M." <mmarszik@gmail.com> - 2017-08-16 07:07 -0700
                Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa bartekltg <bartekltg@gmail.com> - 2017-08-16 15:31 -0700
                  Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa "M.M." <mmarszik@gmail.com> - 2017-08-16 16:12 -0700
                  Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa Borneq <borneq@antyspam.hidden.pl> - 2017-08-17 02:46 +0200
                Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa Tomasz Kaczanowski <kaczus@poczta.onet.pl> - 2017-08-17 08:11 +0200
                  Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa "M.M." <mmarszik@gmail.com> - 2017-08-17 03:26 -0700
      Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa Borneq <borneq@antyspam.hidden.pl> - 2017-08-16 15:46 +0200
        Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa bartekltg <bartekltg@gmail.com> - 2017-08-16 07:06 -0700
      Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa Borneq <borneq@antyspam.hidden.pl> - 2017-08-16 16:05 +0200
        Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa bartekltg <bartekltg@gmail.com> - 2017-08-16 07:11 -0700
          Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa Borneq <borneq@antyspam.hidden.pl> - 2017-08-16 16:22 +0200
            Re: Ciekawy problem iteracyjnego zwalniania głębokiego drzewa "M.M." <mmarszik@gmail.com> - 2017-08-16 07:42 -0700

Page 1 of 2  [1] 2  Next page →

#30223 — Ciekawy problem iteracyjnego zwalniania głębokiego drzewa

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.

[toc] | [next] | [standalone]

#30224

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

[toc] | [prev] | [next] | [standalone]

#30225

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

[toc] | [prev] | [next] | [standalone]

#30226

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?

[toc] | [prev] | [next] | [standalone]

#30227

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.

[toc] | [prev] | [next] | [standalone]

#30229

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.

[toc] | [prev] | [next] | [standalone]

#30230

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

[toc] | [prev] | [next] | [standalone]

#30231

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?

[toc] | [prev] | [next] | [standalone]

#30232

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?

[toc] | [prev] | [next] | [standalone]

#30233

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

[toc] | [prev] | [next] | [standalone]

#30235

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

[toc] | [prev] | [next] | [standalone]

#30237

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

[toc] | [prev] | [next] | [standalone]

#30260

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/a1f5d7a45b08c77414a444462547d8a1

[toc] | [prev] | [next] | [standalone]

#30265

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/a1f5d7a45b08c77414a444462547d8a1

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

[toc] | [prev] | [next] | [standalone]

#30268

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/a1f5d7a45b08c77414a444462547d8a1

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

[toc] | [prev] | [next] | [standalone]

#30271

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.

[toc] | [prev] | [next] | [standalone]

#30277

On Tue, 15 Aug 2017 07:59:17 +0200, Borneq 
<borneq@antyspam.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#.

[toc] | [prev] | [next] | [standalone]

#30279

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?

[toc] | [prev] | [next] | [standalone]

#30282

On Tuesday, August 15, 2017 at 11:58:07 AM UTC+2, slawek wrote:
> On Tue, 15 Aug 2017 07:59:17 +0200, Borneq 
> <borneq@antyspam.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

[toc] | [prev] | [next] | [standalone]

#30283

On Tue, 15 Aug 2017 12:25:59 -0700 (PDT), "M.M." <mmarszik@gmail.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.

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | pl.comp.programming

csiph-web