Меню
Что нового?

Уменьшить количество интераций для постройки дерева

Активист

Активист

Активист
Команда форума
[SQL]
ysql> show create table `faqCategories`\G
*************************** 1. row ***************************
Table: faqCategories
Create Table: CREATE TABLE `faqCategories` (
`id` int(10) unsigned NOT NULL auto_increment,
`parentId` int(10) unsigned default '0',
`urlPart` tinytext,
`url` tinytext,
`title` tinytext,
`description` longtext,
`position` int(11) default NULL,
`lang` tinytext,
PRIMARY KEY (`id`),
KEY `idx_urlPart` (`urlPart`(50)),
KEY `idx_url` (`url`(50)),
KEY `idx_parentId` (`parentId`),
KEY `idx_position` (`position`)
) ENGINE=MyISAM AUTO_INCREMENT=18 DEFAULT CHARSET=cp1251
1 row in set (0.00 sec)

[/SQL]
PHP: 
	public function buildTree(&$objects) {
		$this->_buildTree($objects, false, 0, 0);
		var_dump(faqModel::$inerations);
		//exit();
	}
	
	private function _buildTree(&$objects, $parent, $parentId, $level) {
		foreach ($objects as $key => $object) {
			faqModel::$inerations++;
		
			if ($object->getParentId() == $parentId) {
				$object->setLevel($level);
				
				if ($parent) {
					$parent->addChild($object);
					unset($objects[$key]);
				}
				
				$this->_buildTree($objects, $object, $object->getId(), $level+1);
			}
		}
	}
Есть PHP Код, как уменьшить количетсво интераций. Сейчас на дерево 3-х уровней из 11 обектов идет 72 итерации. Что-то многовато.
 

tz-lom

Продвинутый новичок
PHP: 
public function buildTree($objects)
{
	$relations = array();
	$index = array();
	
	foreach($objects as &$node)		// заполняем таблицы отношений и индексов , O(N)
	{
        $index[$node->getId()] = $node;
        if($node->getParentId()!==false)
        {
            if(isset($index[$node->getParentId()]))		// некоторая оптимизация - если родитель уже был обработан то мы можем связываться сразу а не откладывать на потом
            {
                $index[$node->getParentId()]->addChild($node);
            }
            else
            {
                $relations[$node->getParentId()][] = $node->getId();
            }
        }
	}
	
	foreach($relations as $parent=>$childs) // связываем отношения , O(N)
	{
		foreach($childs as $child)
		{
			$index[$parent]->addChild($index[$child]);
		}
	}
	
	return $index[0]; // или какой там корневой элемент
}
вот как вариант,только с корневым элементом реши что нибудь под свои данные,я не знаю что там у тебя
 
Активист

Активист

Активист
Команда форума
Спасибо :)

PHP: 
	public function buildTree(array &$objects) {
		/** thanks to tz-lom */
		$index = array();
		$relations = array();
		
		foreach($objects as $key => $object) {
			$index[$object->getId()] = $object;
			
			if (isset($index[$object->getParentId()]) && $object->getParentId()) {
				$index[$object->getParentId()]->addChild($object)->setParent($index[$object->getParentId()]);
			} else {
				$relations[$object->getParentId()][] = $object;
			}
		 
		 	if ($object->getParentId()) {
		 		unset($objects[$key]);
		 	}
		 }
		 
		 foreach ($relations as $parent => $childs) {
		 	foreach ($childs as $child) {
		 		if ($parent && isset($index[$parent])) {
		 			$index[$parent]->addChild($child)->setParent($index[$parent]);
		 		}
		 	}
		 }
		 return $this;
	}
Снизилось до 16.
 

vovanium

Новичок
хм, а не проще будет сортировку сделать по parentId, тем более что по нему есть индекс в таблице?
 

tz-lom

Продвинутый новичок
vovanium
в общем смысле сортировка ничего не даст,т.к. идентификаторы не связанны со структурой дерева
 

vovanium

Новичок
tz-lom
это избавляет от необходимости откладывать детей на потом, так как родитель всегда будет до того, как придут дети
 

tz-lom

Продвинутый новичок
vovanium
если бы )

id | parentId
1 | 2
2 | 3
3 | 0
4 | 0
5 | 4
6 | 5
 
Здыхлик

Здыхлик

Kohaner
Команда форума
Вместо parentId можно сортировать по position (я так понимаю, это level узла?)
 
Здыхлик

Здыхлик

Kohaner
Команда форума
Ну да, вполне возможно... Тогда завести level надо! :)

PS. Кстати, зачем int(11) для сортировки заводить? Даже для PK меньше
 

iceman

говнокодер
переходить на Оракл и проблема деревьев решится раз и навсегда =)
 
phprus

phprus

Moderator
Команда форума
iceman
Рекурсивные запросы есть и в PostgreSQL, только несколько в другой форме :)
 
Активист

Активист

Активист
Команда форума
По сортировке не получается, поскольку сортировка локальная на одну ветвь идет (особенности плагина JQuery UI Sortable), нужен глобальный сорт, пока юзаю так (25 интераций):

PHP: 
public function buildTree(array &$objects) {
		/** thanks to tz-lom */
		$index = array();
		$relations = array();
		
		foreach($objects as $key => $object) {
			$index[$object->getId()] = $object->setChilds(array());
			
			/*
			 @todo bug detected - position ordering different results. Need global position system
			 if (isset($index[$object->getParentId()]) && $object->getParentId()) {
				$index[$object->getParentId()]->addChild($object);
			} else {*/
				$relations[$object->getParentId()][] = $object;
			/*}*/
		 
		 	if ($object->getParentId()) {
		 		unset($objects[$key]);
		 	}
		 }
		 
		 foreach ($relations as $parent => $childs) {
		 	foreach ($childs as $child) {
		 		if ($parent && isset($index[$parent])) {
		 			$index[$parent]->addChild($child);
		 		}
		 	}
		 }
		 return $this;
	}
Вообще можно использовать Nested Sets, но сие "чудо" пугает)). Оракл не уважаю, за то что тот скупил MySQL и давит конкурентов, SUN тоже уже у Оракла.

Вообще данный код отличный, помимо сортировки сразу идет обработка детей в виде объектов, что строит отличную картину ООП и не нужно работать с постарением дерева объектов.
 

tz-lom

Продвинутый новичок
Активист
а я думал включать эту оптимизацию или нет,про сортировку совершенно забыл :)
 

Вурдалак

Продвинутый новичок
Извиняюсь за оффтоп, но можно говорить «итерации» вместо «иНтерации»?
 
Войдите или зарегистрируйтесь для ответа.
Сверху