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:



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?

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

Czasem wystarczą odpowiednie pętle, czasem należy użyć już stosów. Wolę to pierwsze rozwiązanie, o ile się da To drugie jest trochę skomplikowane.

spójrz na mój opis: Generator LZT Możesz go dowolnie zmodyfikować, bo nie będzie w 100% wyświetlał tak, jak chcesz Z tym że to jest sposób rekurencyjny.

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?

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

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

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

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

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



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.


Poszukam troche i poczytam, ale dzis juz o tej porze to troche za ciezkie Musze poczekac na dobry dzien.

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

printMe // rekurencja
printMeWithUseOfIterations // iteracja, pewnie da sie przyspieszyc, ale juz mi sie nie chce

[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??
		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 ?




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

printMe: 3.2444250583649
printMeWithUseOfIterations: 3.3689439296722

bez roznicy

Oczywiscie chodzilo o rekurencje w samym php. Przy wysylaniu zapytan to bylaby przesada
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