Witaj Gościu! ( Zaloguj | Rejestruj )

Forum PHP.pl

> Drzewko - podejscie iteracyjne
marcini82
post
Post #1





Grupa: Zarejestrowani
Postów: 190
Pomógł: 1
Dołączył: 20.05.2005
Skąd: Poznań

Ostrzeżenie: (0%)
-----

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
Go to the top of the page
+Quote Post
 
 Start new topic
Odpowiedzi
dr_bonzo
post
Post #2





Grupa: Przyjaciele php.pl
Postów: 5 724
Pomógł: 259
Dołączył: 13.04.2004
Skąd: N/A

Ostrzeżenie: (0%)
-----

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

[PHP] pobierz, plaintext 
  1. <pre><?php
  2.  
  3. $records = array(
  4. 	array( 'id' => 1, 'parent_id' => null, 'name' => '1' ),
  5. 	array( 'id' => 3, 'parent_id' => null, 'name' => '3' ),
  6. 	array( 'id' => 2, 'parent_id' => null, 'name' => '2' ),
  7.  
  8. 	array( 'id' => 4, 'parent_id' => 1, 'name' => '1_1' ),
  9. 	array( 'id' => 5, 'parent_id' => 1, 'name' => '1_2' ),
  10. 	array( 'id' => 6, 'parent_id' => 1, 'name' => '1_3' ),
  11.  
  12. 	array( 'id' => 7, 'parent_id' => 2, 'name' => '2_1' ),
  13. 	array( 'id' => 8, 'parent_id' => 2, 'name' => '2_2' ),
  14.  
  15. 	array( 'id' => 9, 'parent_id' => 3, 'name' => '3_1' )
  16. );
  17.  
  18. $treeObject = createTreeObject( $records );
  19.  
  20. printTree( $treeObject );
  21.  
  22. function createTreeObject( $records )
  23. {
  24. 	$nodeMap = new NodeMap();
  25.  
  26. 	foreach ( $records as $record )
  27. 	{
  28. 		$nodeMap->addNode( new Node( $record['id'], $record['name'], $record['parent_id'] ) );
  29. 	}
  30.  
  31. 	return new Tree( $nodeMap->getTopLevelNodes() );
  32. }
  33.  
  34. function printTree( $tree )
  35. {
  36. 	$tree->printMe();
  37. }
  38.  
  39.  
  40. class Tree
  41. {
  42. 	private $topLevelNodes = array();
  43.  
  44. 	public function __construct( $nodes )
  45. 	{
  46. 		$this->topLevelNodes = $nodes;
  47. 	}
  48.  
  49. 	public function printMe()
  50. 	{
  51. 		foreach ( $this->topLevelNodes as $node )
  52. 		{
  53. 			$this->printNode( $node, 0 );	
  54. 		}
  55. 	}
  56.  
  57. 	// rekurencja !!!
  58. 	private function printNode( $node, $level )
  59. 	{
  60. 		$str = "+" . str_repeat( '-', $level + 1 ) . " " . $node->getName();
  61. 		print( $str . "\n" );
  62.  
  63. 		foreach ( $node->getChildren() as $childNode )
  64. 		{
  65. 			$this->printNode( $childNode, $level + 1 );	
  66. 		}
  67.  
  68. 	}
  69. }
  70.  
  71. class Node
  72. {
  73. 	private $children = array();
  74. 	private $id;
  75. 	private $name;
  76. 	private $parentId;
  77.  
  78. 	public function __construct( $id, $name, $parentId )
  79. 	{
  80. 		$this->id = $id;
  81. 		$this->name = $name;	
  82. 		$this->parentId = $parentId;
  83. 	}
  84.  
  85. 	public function addChild( Node $child )
  86. 	{
  87. 		$this->children[] = $child;
  88. 	}
  89.  
  90. 	public function getChildren()
  91. 	{
  92. 		return $this->children;
  93. 	}
  94.  
  95. 	public function getName()
  96. 	{
  97. 		return $this->name;
  98. 	}
  99.  
  100. 	public function getParentId()
  101. 	{
  102. 		return $this->parentId;
  103. 	}
  104.  
  105. 	public function getId()
  106. 	{
  107. 		return $this->id;
  108. 	}
  109. }
  110.  
  111. class NodeMap
  112. {
  113. 	private $nodes = array();
  114.  
  115. 	private $nodesWaitingToBeAdded = array();
  116.  
  117. 	public function addNode( $node )
  118. 	{
  119. 		$this->nodes[ $node->getId() ] = $node;
  120.  
  121. 		$this->addToParentNode( $node );
  122. 		$this->addWaitingChildren( $node );
  123. 	}
  124.  
  125. 	private function addToParentNode( $node )
  126. 	{
  127. 		$parent = $this->findParent( $node );
  128. 		if ( $parent )
  129. 		{
  130. 			$parent->addChild( $node );
  131. 		}
  132. 		else
  133. 		{
  134. 			$this->markWaitingForParent( $node );
  135. 		}
  136. 	}
  137.  
  138. 	private function findParent( $node )
  139. 	{
  140. 		$parentId = $node->getParentId();
  141. 		$parentExists = isset( $this->nodes[ $parentId ] );
  142. 		if ( $parentExists )
  143. 		{
  144. 			return $this->nodes[ $parentId ];
  145. 		}
  146. 		else
  147. 		{
  148. 			return null;
  149. 		}
  150. 	}
  151.  
  152. 	private function markWaitingForParent( $node )
  153. 	{
  154. 		$thereIsArrayForNodesToBeAdded = isset( $this->nodesWaitingToBeAdded[ $node->getParentId() ] );
  155. 		if ( $thereIsArrayForNodesToBeAdded )
  156. 		{
  157. 			// add next item
  158. 			$this->nodesWaitingToBeAdded[ $node->getParentId() ][] = $node;
  159. 		}
  160. 		else
  161. 		{
  162. 			// create new array
  163. 			$this->nodesWaitingToBeAdded[ $node->getParentId() ] = array( $node );
  164. 		}
  165. 	}
  166.  
  167. 	private function addWaitingChildren( $node )
  168. 	{
  169. 		$thereAreNodesToBeAdded = isset( $this->nodesWaitingToBeAdded[ $node->getId() ] );
  170. 		if ( $thereAreNodesToBeAdded )
  171. 		{
  172. 			$children = $this->nodesWaitingToBeAdded[ $node->getId() ];
  173. 			foreach ( $children as $child )
  174. 			{
  175. 				$node->addChild( $child );	
  176. 			}
  177. 		}
  178.  
  179. 		// remove these, so the only one left will be top level nodes
  180. 		unset( $this->nodesWaitingToBeAdded[ $node->getId() ] );
  181. 	}
  182.  
  183. 	public function getTopLevelNodes()
  184. 	{
  185. 		return $this->nodesWaitingToBeAdded[''];
  186. 	}
  187. }
  188. ?>
  189. </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 
  1. <pre><?php
  2.  
  3. define( 'DEPTH', 10000);
  4. define( 'REPEAT', 100000);
  5.  
  6. $records = array(
  7. 	array( 'id' => 1, 'parent_id' => null, 'name' => '1' ),
  8. 	array( 'id' => 3, 'parent_id' => null, 'name' => '3' ),
  9. 	array( 'id' => 2, 'parent_id' => null, 'name' => '2' ),
  10.  
  11. 	array( 'id' => 4, 'parent_id' => 1, 'name' => '1_1' ),
  12. 	array( 'id' => 5, 'parent_id' => 1, 'name' => '1_2' ),
  13. 	array( 'id' => 6, 'parent_id' => 1, 'name' => '1_3' ),
  14.  
  15. 	array( 'id' => 7, 'parent_id' => 2, 'name' => '2_1' ),
  16. 	array( 'id' => 8, 'parent_id' => 2, 'name' => '2_2' ),
  17.  
  18. 	array( 'id' => 9, 'parent_id' => 3, 'name' => '3_1' )
  19. );
  20.  
  21. /*
  22.  
  23. glebokie drzewko
  24. $records = array();
  25.  
  26. $item = array('id' => 1, 'parent_id' => null, 'name' => '1' );
  27. for ( $j = 2; $j < DEPTH; $j++ )
  28. {
  29. 	$records[] = array( 'id' => $j, 'parent_id' => ($j - 1), 'name' => 'blah' );
  30. }
  31. */
  32.  
  33.  
  34.  
  35.  
  36. $treeObject = createTreeObject( $records );
  37.  
  38. printTree( $treeObject );
  39.  
  40. function createTreeObject( $records )
  41. {
  42. 	$nodeMap = new NodeMap();
  43.  
  44. 	foreach ( $records as $record )
  45. 	{
  46. 		$nodeMap->addNode( new Node( $record['id'], $record['name'], $record['parent_id'] ) );
  47. 	}
  48.  
  49. 	return new Tree( $nodeMap->getTopLevelNodes() );
  50. }
  51.  
  52. function printTree( $tree )
  53. {
  54. 	benchmark( $tree, 'printMe' );
  55. 	benchmark( $tree, 'printMeWithUseOfIterations' );
  56. }
  57.  
  58. function benchmark( $tree, $func )
  59. {
  60.  
  61. 	$start = microtime( true );
  62. 	for ( $i = 0; $i < REPEAT; $i++ )
  63. 	{
  64. 		$tree->$func();
  65. 	}
  66. 	$end = microtime( true );
  67.  
  68. 	print( "$func: " . ( $end - $start ) . "\n" );
  69. }
  70.  
  71.  
  72. class Tree
  73. {
  74. 	private $topLevelNodes = array();
  75.  
  76. 	public function __construct( $nodes )
  77. 	{
  78. 		$this->topLevelNodes = $nodes;
  79. 	}
  80.  
  81. 	public function printMeWithUseOfIterations()
  82. 	{
  83. 		$todoNodes = array_reverse( $this->topLevelNodes );
  84. 		$currentProcessedNodes = array();
  85.  
  86. 		$level = 0;
  87. 		// on extract -> increase?(IMG:http://forum.php.pl/style_emoticons/default/questionmark.gif) ?
  88. 		while ( ! ( empty( $todoNodes ) && empty( $currentProcessedNodes ) ) )
  89. 		{
  90. 			if ( empty( $currentProcessedNodes ) )
  91. 			{
  92. 				// remove node from TODO and return it
  93. 				$firstNodeTodo = array_pop( $todoNodes );
  94. 				$currentProcessedNodes[] = $firstNodeTodo;
  95. 			}
  96.  
  97. 			$nextNode = array_pop( $currentProcessedNodes ); // the last one: remove and return
  98.  
  99. 			//print($nextNode->getName() . "\n" );
  100.  
  101. 			$reversedChildren = array_reverse( $nextNode->getChildren() );
  102. 			$currentProcessedNodes = array_merge( $currentProcessedNodes, $reversedChildren );
  103. 		}
  104. 	}
  105.  
  106. 	public function printMe()
  107. 	{
  108. 		foreach ( $this->topLevelNodes as $node )
  109. 		{
  110. 			$this->printNode( $node, 0 );	
  111. 		}
  112. 	}
  113.  
  114. 	// rekurencja !!!
  115. 	private function printNode( $node, $level )
  116. 	{
  117. 		$str = "+" . str_repeat( '-', $level + 1 ) . " " . $node->getName();
  118. 		//print( $str . "\n" );
  119.  
  120. 		foreach ( $node->getChildren() as $childNode )
  121. 		{
  122. 			$this->printNode( $childNode, $level + 1 );	
  123. 		}
  124.  
  125. 	}
  126. }
  127.  
  128. class Node
  129. {
  130. 	private $children = array();
  131. 	private $id;
  132. 	private $name;
  133. 	private $parentId;
  134.  
  135. 	public function __construct( $id, $name, $parentId )
  136. 	{
  137. 		$this->id = $id;
  138. 		$this->name = $name;	
  139. 		$this->parentId = $parentId;
  140. 	}
  141.  
  142. 	public function addChild( Node $child )
  143. 	{
  144. 		$this->children[] = $child;
  145. 	}
  146.  
  147. 	public function getChildren()
  148. 	{
  149. 		return $this->children;
  150. 	}
  151.  
  152. 	public function getName()
  153. 	{
  154. 		return $this->name;
  155. 	}
  156.  
  157. 	public function getParentId()
  158. 	{
  159. 		return $this->parentId;
  160. 	}
  161.  
  162. 	public function getId()
  163. 	{
  164. 		return $this->id;
  165. 	}
  166. }
  167.  
  168. class NodeMap
  169. {
  170. 	private $nodes = array();
  171.  
  172. 	private $nodesWaitingToBeAdded = array();
  173.  
  174. 	public function addNode( $node )
  175. 	{
  176. 		$this->nodes[ $node->getId() ] = $node;
  177.  
  178. 		$this->addToParentNode( $node );
  179. 		$this->addWaitingChildren( $node );
  180. 	}
  181.  
  182. 	private function addToParentNode( $node )
  183. 	{
  184. 		$parent = $this->findParent( $node );
  185. 		if ( $parent )
  186. 		{
  187. 			$parent->addChild( $node );
  188. 		}
  189. 		else
  190. 		{
  191. 			$this->markWaitingForParent( $node );
  192. 		}
  193. 	}
  194.  
  195. 	private function findParent( $node )
  196. 	{
  197. 		$parentId = $node->getParentId();
  198. 		$parentExists = isset( $this->nodes[ $parentId ] );
  199. 		if ( $parentExists )
  200. 		{
  201. 			return $this->nodes[ $parentId ];
  202. 		}
  203. 		else
  204. 		{
  205. 			return null;
  206. 		}
  207. 	}
  208.  
  209. 	private function markWaitingForParent( $node )
  210. 	{
  211. 		$thereIsArrayForNodesToBeAdded = isset( $this->nodesWaitingToBeAdded[ $node->getParentId() ] );
  212. 		if ( $thereIsArrayForNodesToBeAdded )
  213. 		{
  214. 			// add next item
  215. 			$this->nodesWaitingToBeAdded[ $node->getParentId() ][] = $node;
  216. 		}
  217. 		else
  218. 		{
  219. 			// create new array
  220. 			$this->nodesWaitingToBeAdded[ $node->getParentId() ] = array( $node );
  221. 		}
  222. 	}
  223.  
  224. 	private function addWaitingChildren( $node )
  225. 	{
  226. 		$thereAreNodesToBeAdded = isset( $this->nodesWaitingToBeAdded[ $node->getId() ] );
  227. 		if ( $thereAreNodesToBeAdded )
  228. 		{
  229. 			$children = $this->nodesWaitingToBeAdded[ $node->getId() ];
  230. 			foreach ( $children as $child )
  231. 			{
  232. 				$node->addChild( $child );	
  233. 			}
  234. 		}
  235.  
  236. 		// remove these, so the only one left will be top level nodes
  237. 		unset( $this->nodesWaitingToBeAdded[ $node->getId() ] );
  238. 	}
  239.  
  240. 	public function getTopLevelNodes()
  241. 	{
  242. 		$nodes = array();
  243. 		foreach ( $this->nodes as $node )
  244. 		{
  245. 			if ( is_null( $node->getParentId() ) )
  246. 			{
  247. 				$nodes[] = $node;	
  248. 			}
  249. 		}
  250.  
  251. 		return $nodes;
  252. 	}
  253. }
  254. ?>
  255. </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
Go to the top of the page
+Quote Post

Posty w temacie
- marcini82   Drzewko - podejscie iteracyjne   13.09.2007, 12:37:10
- - qqrq   Poszukaj na forum - kilka takich tematów już było....   13.09.2007, 13:04:41
|- - pbnan   Cytat(qqrq @ 13.09.2007, 14:04:41 ) W...   14.09.2007, 15:42:06
- - radex_p   spójrz na mój opis: Generator LZT Możesz go ...   14.09.2007, 15:58:42
- - marcini82   Rekurencyjnie to umiem - zaden problem. Ale chci...   28.09.2007, 13:14:54
|- - pbnan   Cytat(marcini82 @ 28.09.2007, 14:14:5...   28.09.2007, 15:37:40
- - vaca   Istnieje podejście, choć oczywiście o innej strukt...   28.09.2007, 14:59:29
- - dr_bonzo   CytatOdczytalismy te rekordy z bazy, mamy je w dwu...   28.09.2007, 20:46:36
- - marcini82   CytatPokaz ta tablice bo nie potrafie sobie jej wy...   29.09.2007, 22:41:16
- - dr_bonzo   marcini82: najpierw myslalem ze chodzi ci o rekure...   30.09.2007, 00:20:53
- - marcini82   Oczywiscie chodzilo o rekurencje w samym php. Przy...   2.10.2007, 19:20:41

« Następny starszy · PHP · Następny nowszy »
 

Reply to this topicStart new topic
2 Użytkowników czyta ten temat (2 Gości i 0 Anonimowych użytkowników)
0 Zarejestrowanych:

 

Tryb wyświetlania: Przełącz na: Standardowy · Przełącz na: Linearny+ · Drzewo

Śledź ten temat · Wyślij temat na e-mail · Wydrukuj ten temat · Subskrybuj to forum

RSS Aktualny czas: 10.10.2025 - 22:34
Powered By IP.Board © 2025  IPS, Inc.
All changes by PHP.pl Administrators
Hosting zapewnia NQ.pl hosting, trac, svn