Jump to content
php.lv forumi

koka būves algoritms?


john.brown

Recommended Posts

Tātad dabonu es no db ierakstus ar ceļiem uz mapītēm:

folder_1
folder_1/folder_1_1
folder_1/folder_1_2
...

Gribētos uztaisīt no šamiem smuku masīvu, apm. tādu:

$items = array(
'folder_1' => array('path' => $path,
				'name'=> $name,
				'tree' => array(
								'folder_1_1' => array('path' => $path,
													  'name' => $name, 
													  'tree' => array()), 
								'folder_1_2' =>	array('path' => $path,
													  'name' => $name, 
													  'tree' => array())
								)
			)
);

Piedevām, var būt situācija, kad tanī sarakstā ir folder_2/folder_2_1, bet nav folder_2. Esmu baigi iebremzējies, un galīgi nesaprotu, ka to smuki dabūt gatavu. Moš, var kāds palīdzēt ar idejām?

Link to comment
Share on other sites

He, jau paspēju pats ko strādājošu sacerēt. Vismaz pagaidām tā izskatās...

$data = array('folder_1','folder_1/folder_1_1','folder_1/folder_1_2','folder_2/folder_2_1');

$items = array('name' => 'root','path' => '','tree' => array());

foreach($data as $path) {
	$parts = explode('/',$path);
	$curr_node = & $items;
	$item_path = '';
	do{
		$p = array_shift($parts);
		$item_path.= '/'.$p;
		if(!isset($curr_node['tree'][$p])) {
			$curr_node['tree'][$p] = array('name' => $p, 'path' => $item_path,'tree' => array());	
		}
		$curr_node = & $curr_node['tree'][$p];	
	}while($parts);	
}
echo '<pre>';
print_r($items);

 

Varbūt kādi ieteikumi uzlabošanas jomā? Vai pavisam kā prastāk?

Link to comment
Share on other sites

Nav gan labāk. Ja var uzrakstīt diezgan vienkāršu iteratīvu algoritmu, tad noteikti to vajag darīt, nevis izmantot rekursiju. Rekursija "piemēslo" steku, tātad arī kešatmiņu. Iteratīvam algoritmam vispārīgā gadījumā, ja vien tas nesarežģī algoritmu, jābūt ātrākam par rekursiju.

 

Pie tam, rekursija ar rekursīvo izsaukumu funkcijas beigās (tieši tāds ir šis gadījums) diezgan triviāli pārveidojas uz iteratīvu algoritmu (tieši tādu kādu uzrakstīja john.brown).

 

Nevajag šaut ar liegabalu pa zvirbuļiem!

Link to comment
Share on other sites

×
×
  • Create New...