Drzewko - podejscie iteracyjne Opcje

[marcini82]

Witam!

Zalozmy, ze mamy w tabeli bazy danych proste drzewko. Kazdy wiersz ma 3 pola: id, parent_id i name.
Odczytalismy te rekordy z bazy, mamy je w dwuwymiarowej tablicy asocjacyjnej i chcemy wyswietlic w formie drzewka:

Kod

level1_1
    level2_1
        level3_1
        level3_2
        level3_3
    level2_2
    level2_3
level1_2
    level2_4
level1_3

Drzewko moze miec dowolna ilosc poziomow zaglebienia.
Jesli sie uzywa rekurencji to proste. Ale czy da sie to zrobic iteracyjnie? A jesli sie da, to jak?
Zakladam, ze jesli sie da, to bedzie wydajniej. Czy sie nie myle?

Ten post edytował marcini82 13.09.2007, 12:37:51

[qqrq]

Poszukaj na forum - kilka takich tematów już było.

A co do przewagi iteracji nad rekurencją - pętle są szybsze, to prawda. Wogóle nie wiem czy wiecie, ale każdą rekurencję można przerobić na iterację. W prawdzie, wstyd się przyznać, nie wiem dokładnie jak, ale podobno można... (IMG:http://forum.php.pl/style_emoticons/default/smile.gif)

[pbnan]

Wogóle nie wiem czy wiecie, ale każdą rekurencję można przerobić na iterację. W prawdzie, wstyd się przyznać, nie wiem dokładnie jak, ale podobno można... (IMG:http://forum.php.pl/style_emoticons/default/smile.gif)

Czasem wystarczą odpowiednie pętle, czasem należy użyć już stosów. Wolę to pierwsze rozwiązanie, o ile się da (IMG:http://forum.php.pl/style_emoticons/default/snitch.gif) To drugie jest trochę skomplikowane.

[.radex]

spójrz na mój opis: Generator LZT (IMG:http://forum.php.pl/style_emoticons/default/smile.gif) Możesz go dowolnie zmodyfikować, bo nie będzie w 100% wyświetlał tak, jak chcesz (IMG:http://forum.php.pl/style_emoticons/default/smile.gif) Z tym że to jest sposób rekurencyjny.

Ten post edytował radex_p 15.09.2007, 17:13:22

[marcini82]

Rekurencyjnie to umiem - zaden problem.

Ale chcialbym sobie cos takiego zrobic bez rekurencji i porownac wydajnosc. Jak moge obsluzyc te nieograniczona ilosc poziomow zaglebienia?
Moze byscie mogli rzucic jakimis przykladami? Cokolwiek, co by mi pozwolilo zalapac idee tego podejscia?

@pbnan
Piszesz o stosach. A moglbys dac jakis przyklad ich wykorzystania w podobnym problemie?

[vaca]

Istnieje podejście, choć oczywiście o innej strukturze danych niż opisana przez Ciebie. Ale rzeczywiście zwieksza wydajnosc:
wygugluj sobie 'celko tree'.

[pbnan]

@pbnan
Piszesz o stosach. A moglbys dac jakis przyklad ich wykorzystania w podobnym problemie?

Mam to w książce "Algorytmy i struktury danych" wyd. Helion. Niestety, trudny temat, jak na początek odpuściłem sobie go i wiele powiedzieć nie mogę.
Natomiast wygóglować można ciekawe informacje.
Np. tutaj [cache gógla] masz coś o tym: http://209.85.135.104/search?q=cache:SWFf8...t=clnk&cd=6

[dr_bonzo]

Odczytalismy te rekordy z bazy, mamy je w dwuwymiarowej tablicy asocjacyjnej i chcemy wyswietlic w formie drzewka:

Pokaz ta tablice bo nie potrafie sobie jej wyobrazic, i jak jest posortowana.

Co do rekurencji - ograniczona jest wielkoscia stosu == glebokosci drzewka

[marcini82]

Pokaz ta tablice bo nie potrafie sobie jej wyobrazic, i jak jest posortowana.

Przedstawia po prostu kolejne rekordy w bazie danych przy takim modelu drzewka:

Kod

Array
(
    [0] => Array
        (
            [id] => 2
            [name] => level1_1
            [parent_id] => 1
        )

    [1] => Array
        (
            [id] => 3
            [name] => level1_2
            [parent_id] => 1
        )

    [2] => Array
        (
            [id] => 4
            [name] => level1_3
            [parent_id] => 1
        )

    [3] => Array
        (
            [id] => 5
            [name] => level2_1
            [parent_id] => 2
        )

    [4] => Array
        (
            [id] => 6
            [name] => level2_2
            [parent_id] => 2
        )

    [5] => Array
        (
            [id] => 7
            [name] => level2_3
            [parent_id] => 2
        )

)

Istnieje podejście, choć oczywiście o innej strukturze danych niż opisana przez Ciebie. Ale rzeczywiście zwieksza wydajnosc:
wygugluj sobie 'celko tree'.

Chodzi ci o "nested sets"? Tez ciekawy temat, ogolnie drzewka to dosc obszerna i zawila sprawa, bo kazde podejscie ma plusy i minusy...
Ale w tej chwili zalezy mi glownie na wyrzuceniu rekurencji z tego konkretnego modelu drzewka.

Mam to w książce "Algorytmy i struktury danych" wyd. Helion. Niestety, trudny temat, jak na początek odpuściłem sobie go i wiele powiedzieć nie mogę.
Natomiast wygóglować można ciekawe informacje.

Poszukam troche i poczytam, ale dzis juz o tej porze to troche za ciezkie (IMG:http://forum.php.pl/style_emoticons/default/winksmiley.jpg) Musze poczekac na dobry dzien.

[dr_bonzo]

marcini82: najpierw myslalem ze chodzi ci o rekurencje w samym php, a nie przy pobieraniu parentow z bazy, tak?

[PHP] pobierz, plaintext 
<pre><?php
 
$records = array(
	array( 'id' => 1, 'parent_id' => null, 'name' => '1' ),
	array( 'id' => 3, 'parent_id' => null, 'name' => '3' ),
	array( 'id' => 2, 'parent_id' => null, 'name' => '2' ),
 
	array( 'id' => 4, 'parent_id' => 1, 'name' => '1_1' ),
	array( 'id' => 5, 'parent_id' => 1, 'name' => '1_2' ),
	array( 'id' => 6, 'parent_id' => 1, 'name' => '1_3' ),
 
	array( 'id' => 7, 'parent_id' => 2, 'name' => '2_1' ),
	array( 'id' => 8, 'parent_id' => 2, 'name' => '2_2' ),
 
	array( 'id' => 9, 'parent_id' => 3, 'name' => '3_1' )
);
 
$treeObject = createTreeObject( $records );
 
printTree( $treeObject );
 
function createTreeObject( $records )
{
	$nodeMap = new NodeMap();
 
	foreach ( $records as $record )
	{
		$nodeMap->addNode( new Node( $record['id'], $record['name'], $record['parent_id'] ) );
	}
 
	return new Tree( $nodeMap->getTopLevelNodes() );
}
 
function printTree( $tree )
{
	$tree->printMe();
}
 
 
class Tree
{
	private $topLevelNodes = array();
 
	public function __construct( $nodes )
	{
		$this->topLevelNodes = $nodes;
	}
 
	public function printMe()
	{
		foreach ( $this->topLevelNodes as $node )
		{
			$this->printNode( $node, 0 );	
		}
	}
 
	// rekurencja !!!
	private function printNode( $node, $level )
	{
		$str = "+" . str_repeat( '-', $level + 1 ) . " " . $node->getName();
		print( $str . "\n" );
 
		foreach ( $node->getChildren() as $childNode )
		{
			$this->printNode( $childNode, $level + 1 );	
		}
 
	}
}
 
class Node
{
	private $children = array();
	private $id;
	private $name;
	private $parentId;
 
	public function __construct( $id, $name, $parentId )
	{
		$this->id = $id;
		$this->name = $name;	
		$this->parentId = $parentId;
	}
 
	public function addChild( Node $child )
	{
		$this->children[] = $child;
	}
 
	public function getChildren()
	{
		return $this->children;
	}
 
	public function getName()
	{
		return $this->name;
	}
 
	public function getParentId()
	{
		return $this->parentId;
	}
 
	public function getId()
	{
		return $this->id;
	}
}
 
class NodeMap
{
	private $nodes = array();
 
	private $nodesWaitingToBeAdded = array();
 
	public function addNode( $node )
	{
		$this->nodes[ $node->getId() ] = $node;
 
		$this->addToParentNode( $node );
		$this->addWaitingChildren( $node );
	}
 
	private function addToParentNode( $node )
	{
		$parent = $this->findParent( $node );
		if ( $parent )
		{
			$parent->addChild( $node );
		}
		else
		{
			$this->markWaitingForParent( $node );
		}
	}
 
	private function findParent( $node )
	{
		$parentId = $node->getParentId();
		$parentExists = isset( $this->nodes[ $parentId ] );
		if ( $parentExists )
		{
			return $this->nodes[ $parentId ];
		}
		else
		{
			return null;
		}
	}
 
	private function markWaitingForParent( $node )
	{
		$thereIsArrayForNodesToBeAdded = isset( $this->nodesWaitingToBeAdded[ $node->getParentId() ] );
		if ( $thereIsArrayForNodesToBeAdded )
		{
			// add next item
			$this->nodesWaitingToBeAdded[ $node->getParentId() ][] = $node;
		}
		else
		{
			// create new array
			$this->nodesWaitingToBeAdded[ $node->getParentId() ] = array( $node );
		}
	}
 
	private function addWaitingChildren( $node )
	{
		$thereAreNodesToBeAdded = isset( $this->nodesWaitingToBeAdded[ $node->getId() ] );
		if ( $thereAreNodesToBeAdded )
		{
			$children = $this->nodesWaitingToBeAdded[ $node->getId() ];
			foreach ( $children as $child )
			{
				$node->addChild( $child );	
			}
		}
 
		// remove these, so the only one left will be top level nodes
		unset( $this->nodesWaitingToBeAdded[ $node->getId() ] );
	}
 
	public function getTopLevelNodes()
	{
		return $this->nodesWaitingToBeAdded[''];
	}
}
?>
</pre>
[PHP] pobierz, plaintext 

Co to robi? Przerabia rekordy na drzewko Node'ow i drukuje je. Zachowuje kolejnosc rekordow z bazy, tzn jesli 1_2 bylo przed 1_1 to tak zostana wyswietlone
Niestety jest rekurencja (bo nie chcialo mi sie rozpisywac) O takie cos chodzilo?
Zeby pozbyc sie tej rekurencji trzeba zasymulowac zachowanie stosu przy korzystaniu z rekurencji. Chyba zaraz to napisze (IMG:http://forum.php.pl/style_emoticons/default/smile.gif)

printMe // rekurencja
printMeWithUseOfIterations // iteracja, pewnie da sie przyspieszyc, ale juz mi sie nie chce (IMG:http://forum.php.pl/style_emoticons/default/biggrin.gif)

[PHP] pobierz, plaintext 
<pre><?php
 
define( 'DEPTH', 10000);
define( 'REPEAT', 100000);
 
$records = array(
	array( 'id' => 1, 'parent_id' => null, 'name' => '1' ),
	array( 'id' => 3, 'parent_id' => null, 'name' => '3' ),
	array( 'id' => 2, 'parent_id' => null, 'name' => '2' ),
 
	array( 'id' => 4, 'parent_id' => 1, 'name' => '1_1' ),
	array( 'id' => 5, 'parent_id' => 1, 'name' => '1_2' ),
	array( 'id' => 6, 'parent_id' => 1, 'name' => '1_3' ),
 
	array( 'id' => 7, 'parent_id' => 2, 'name' => '2_1' ),
	array( 'id' => 8, 'parent_id' => 2, 'name' => '2_2' ),
 
	array( 'id' => 9, 'parent_id' => 3, 'name' => '3_1' )
);
 
/*
 
glebokie drzewko
$records = array();
 
$item = array('id' => 1, 'parent_id' => null, 'name' => '1' );
for ( $j = 2; $j < DEPTH; $j++ )
{
	$records[] = array( 'id' => $j, 'parent_id' => ($j - 1), 'name' => 'blah' );
}
*/
 
 
 
 
$treeObject = createTreeObject( $records );
 
printTree( $treeObject );
 
function createTreeObject( $records )
{
	$nodeMap = new NodeMap();
 
	foreach ( $records as $record )
	{
		$nodeMap->addNode( new Node( $record['id'], $record['name'], $record['parent_id'] ) );
	}
 
	return new Tree( $nodeMap->getTopLevelNodes() );
}
 
function printTree( $tree )
{
	benchmark( $tree, 'printMe' );
	benchmark( $tree, 'printMeWithUseOfIterations' );
}
 
function benchmark( $tree, $func )
{
 
	$start = microtime( true );
	for ( $i = 0; $i < REPEAT; $i++ )
	{
		$tree->$func();
	}
	$end = microtime( true );
 
	print( "$func: " . ( $end - $start ) . "\n" );
}
 
 
class Tree
{
	private $topLevelNodes = array();
 
	public function __construct( $nodes )
	{
		$this->topLevelNodes = $nodes;
	}
 
	public function printMeWithUseOfIterations()
	{
		$todoNodes = array_reverse( $this->topLevelNodes );
		$currentProcessedNodes = array();
 
		$level = 0;
		// on extract -> increase?(IMG:http://forum.php.pl/style_emoticons/default/questionmark.gif) ?
		while ( ! ( empty( $todoNodes ) && empty( $currentProcessedNodes ) ) )
		{
			if ( empty( $currentProcessedNodes ) )
			{
				// remove node from TODO and return it
				$firstNodeTodo = array_pop( $todoNodes );
				$currentProcessedNodes[] = $firstNodeTodo;
			}
 
			$nextNode = array_pop( $currentProcessedNodes ); // the last one: remove and return
 
			//print($nextNode->getName() . "\n" );
 
			$reversedChildren = array_reverse( $nextNode->getChildren() );
			$currentProcessedNodes = array_merge( $currentProcessedNodes, $reversedChildren );
		}
	}
 
	public function printMe()
	{
		foreach ( $this->topLevelNodes as $node )
		{
			$this->printNode( $node, 0 );	
		}
	}
 
	// rekurencja !!!
	private function printNode( $node, $level )
	{
		$str = "+" . str_repeat( '-', $level + 1 ) . " " . $node->getName();
		//print( $str . "\n" );
 
		foreach ( $node->getChildren() as $childNode )
		{
			$this->printNode( $childNode, $level + 1 );	
		}
 
	}
}
 
class Node
{
	private $children = array();
	private $id;
	private $name;
	private $parentId;
 
	public function __construct( $id, $name, $parentId )
	{
		$this->id = $id;
		$this->name = $name;	
		$this->parentId = $parentId;
	}
 
	public function addChild( Node $child )
	{
		$this->children[] = $child;
	}
 
	public function getChildren()
	{
		return $this->children;
	}
 
	public function getName()
	{
		return $this->name;
	}
 
	public function getParentId()
	{
		return $this->parentId;
	}
 
	public function getId()
	{
		return $this->id;
	}
}
 
class NodeMap
{
	private $nodes = array();
 
	private $nodesWaitingToBeAdded = array();
 
	public function addNode( $node )
	{
		$this->nodes[ $node->getId() ] = $node;
 
		$this->addToParentNode( $node );
		$this->addWaitingChildren( $node );
	}
 
	private function addToParentNode( $node )
	{
		$parent = $this->findParent( $node );
		if ( $parent )
		{
			$parent->addChild( $node );
		}
		else
		{
			$this->markWaitingForParent( $node );
		}
	}
 
	private function findParent( $node )
	{
		$parentId = $node->getParentId();
		$parentExists = isset( $this->nodes[ $parentId ] );
		if ( $parentExists )
		{
			return $this->nodes[ $parentId ];
		}
		else
		{
			return null;
		}
	}
 
	private function markWaitingForParent( $node )
	{
		$thereIsArrayForNodesToBeAdded = isset( $this->nodesWaitingToBeAdded[ $node->getParentId() ] );
		if ( $thereIsArrayForNodesToBeAdded )
		{
			// add next item
			$this->nodesWaitingToBeAdded[ $node->getParentId() ][] = $node;
		}
		else
		{
			// create new array
			$this->nodesWaitingToBeAdded[ $node->getParentId() ] = array( $node );
		}
	}
 
	private function addWaitingChildren( $node )
	{
		$thereAreNodesToBeAdded = isset( $this->nodesWaitingToBeAdded[ $node->getId() ] );
		if ( $thereAreNodesToBeAdded )
		{
			$children = $this->nodesWaitingToBeAdded[ $node->getId() ];
			foreach ( $children as $child )
			{
				$node->addChild( $child );	
			}
		}
 
		// remove these, so the only one left will be top level nodes
		unset( $this->nodesWaitingToBeAdded[ $node->getId() ] );
	}
 
	public function getTopLevelNodes()
	{
		$nodes = array();
		foreach ( $this->nodes as $node )
		{
			if ( is_null( $node->getParentId() ) )
			{
				$nodes[] = $node;	
			}
		}
 
		return $nodes;
	}
}
?>
</pre>
[PHP] pobierz, plaintext 

Wyszlo mi

dla glebokiego drzewka :
define( 'DEPTH', 10000); define( 'REPEAT', 100000);

printMe: 0.088973999023438
printMeWithUseOfIterations: 0.26687598228455

rekurencja rzadzi ? (IMG:http://forum.php.pl/style_emoticons/default/biggrin.gif)




dla "szerokiego"
define( 'REPEAT', 100000);

printMe: 3.2444250583649
printMeWithUseOfIterations: 3.3689439296722

bez roznicy

[marcini82]

Oczywiscie chodzilo o rekurencje w samym php. Przy wysylaniu zapytan to bylaby przesada (IMG:http://forum.php.pl/style_emoticons/default/winksmiley.jpg)
Musze przyznac, ze odwaliles kawal dobrej roboty z tym przykladem. Chociaz obszernosc tego kodu nieco utrudnia dotarcie do samego sposobu eliminacji rekurencji... Musze to dokladniej przeanalizowac.

Zdziwily mnie te wyniki. Co prawda rekurencja w php to troche co innego niz w jezykach nizszego poziomu, ale mimo wszystko spodziewalem sie jednak spadku wydajnosci.

Zrobilem jeszcze taki tescik:

[PHP] pobierz, plaintext 
<?php
function rek($num){
	if($num < 1450){
		echo $num.'<br/>';
		rek($num+1);
	}
}
 
rek(1);
?>
[PHP] pobierz, plaintext 

Wyglada na to, ze php wyklada sie jesli ilosc wywolan rekurencyjnych przekracza 1400-1500. W sumie to dosc duzo. Daloby sie spore drzewo wyrysowac (IMG:http://forum.php.pl/style_emoticons/default/biggrin.gif)