koka būves algoritms?

[john.brown]

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?

[bubu]

katram stringam:

* explore pa /

* iet caur iegūtā masīva elementiem un veido vai nu tukšu array(path, name tree=array()) esošā masīvā, ja vēl tāda nav, vai paņem masīva elementu items = items[curent]['tree']

[john.brown]

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?

[Blitz]

Labak nav izmantot kadu rekursiju kas taisa n limenu tree?

[blackhalt]

Ir

[bubu]

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!