Рекурсивный массив

solovin1986 · June 23, 2011

Есть база


id|parentid|posi|name
 1|———--0|--—0|Россия
 2|———--1|--—0|Центр
 3|———--2|—--0|Москва и область
 4|———--3|—--0|Москва
 5|———--3|--—1|Долгопрудный
 6|———--3|—--0|Дубна
 7|———--0|—--0|Украина

Есть код

function get_region_arr($parentid = 0) {
	global $db;
	$db->query("SELECT * FROM " . PREFIX . "_region WHERE parentid = '$parentid' ORDER BY parentid, posi ASC");
	while ( $row = $db->get_row() ) {
		$arr[$row['id']] = $row['name'];
	}
	return $arr;
}

print '<pre>'. print_r(get_region_arr(), true) . '</pre>';

Результат

Array
(
    [1] => Россия
    [7] => Украина
)

КАК СОЗДАТЬ РЕКУРСИВНЫЙ МАССИВ.

ПОМОГИТЕ ПЛУЖУ УЖЕ ВТОРОЙ ДЕНЬ

Veseloff · June 24, 2011

Как я писал выше, я подобную задачу даю на собеседования. Вот условия:

Программист Бхвагтан имеет свой официальный сайт на котором он рассказывает о том какой он молодец и чего достиг в жизни. Есть на этом сайте форма для того, чтобы можно было оставить комментарий или, например, вопрос Бхвагтану. Каждый оставленный комментарий можно так же комментировать. Все комментарии хранятся в таблице MySQL.
--------------------------------------------------------------------------------------------------
CREATE TABLE IF NOT EXISTS `comments` (
`id` int(11) NOT NULL AUTO_INCREMENT,
`parent` int(11) DEFAULT NULL,
`name` varchar(255) DEFAULT NULL,
`comment` text,
PRIMARY KEY (`id`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8 AUTO_INCREMENT=14 ;
INSERT INTO `comments` (`id`, `parent`, `name`, `comment`) VALUES
(4, 0, 'Вася', 'Вот мой первый комментарий'),
(5, 4, 'Федя', 'Отвечаю на первый комментарий'),
(6, 5, 'Вася', 'Отвечаю на ответ'),
(7, 5, 'Пётр', 'Я тоже отвечаю на ответ'),
(8, 7, 'Иван', 'А я отвечаю Петру'),
(9, 0, 'Игорь', 'А вот ещё коммент первого уровня'),
(10, 0, 'Тамара', 'Девушка врывается в тред!'),
(11, 10, 'Федя', 'Привет, Тамара!'),
(12, 11, 'Тамара', 'Привет, Фёдор'),
(13, 10, 'Иван', 'Привет, Тамара, я Иван. А тебя как зовут?');
--------------------------------------------------------------------------------------------------
Как видно из дампа, у каждого комментария есть свой уникальный id и ссылка на комментарий, на который он отвечает. В случае, если комментируется пост, вместо id «родителя» стоит 0 (ноль). Так же хранятся в записи имя комментирующего и собственно текст комментария. Необходимо написать скрипт, который из данных этой таблицы построит следующий массив:
--------------------------------------------------------------------------------------------------
Array
(
[4] => Array
(
[id] => 4
[parent] => 0
[name] => Вася
[comment] => Вот мой первый комментарий
[children] => Array
(
[5] => Array
(
[id] => 5
[parent] => 4
[name] => Федя
[comment] => Отвечаю на первый комментарий
[children] => Array
(
[6] => Array
(
[id] => 6
[parent] => 5
[name] => Вася
[comment] => Отвечаю на ответ
)
[7] => Array
(
[id] => 7
[parent] => 5
[name] => Пётр
[comment] => Я тоже отвечаю на ответ
[children] => Array
(
[8] => Array
(
[id] => 8
[parent] => 7
[name] => Иван
[comment] => А я отвечаю Петру
)
)
)
)
)
)
)
[9] => Array
(
[id] => 9
[parent] => 0
[name] => Игорь
[comment] => А вот ещё коммент первого уровня
)
[10] => Array
(
[id] => 10
[parent] => 0
[name] => Тамара
[comment] => Девушка врывается в тред!
[children] => Array
(
[11] => Array
(
[id] => 11
[parent] => 10
[name] => Федя
[comment] => Привет, Тамара!
[children] => Array
(
[12] => Array
(
[id] => 12
[parent] => 11
[name] => Тамара
[comment] => Привет, Фёдор
)
)
)
[13] => Array
(
[id] => 13
[parent] => 10
[name] => Иван
[comment] => Привет, Тамара, я Иван. А тебя как зовут?
)
)
)
)

А вот как я вижу решение этой задачи.

<?php
$db=new MySQLi('localhost', 'username', 'password', 'test');

$q=$db->query("SELECT * FROM `comments` ORDER BY `parent` ASC, `id` ASC");

$tree=array(0=>array('id'=>0, 'parent'=>0, 'comment'=>'root'));
$temp=array(0=>&$tree[0]);

while ($r=$q->fetch_assoc())
{
	$parent = &$temp[$r['parent']];
	if (!isset($parent['children'])) $parent['children'] = array();
	$parent['children'][$r['id']] = $r;
	$temp[$r['id']] = &$parent['children'][$r['id']];
}

$res=isset($tree[0]['children']) ? $tree[0]['children'] : array();

print_r($res);

Она, конечно отличается от той, что писал топикстартер, но суть абсолтно такая же.

P.S. Для того, чтобы на 100% успешно пройти собеседование, соискателю необходимо так же тонко подметить, что поле parent должно быть NOT NULL, а так же на него надо навесить индекc.

solovin1986 · June 24, 2011

По поводу NOT NULL это высказывание абсурд, так как при добавлении в базу оно автоматом будет 0 так как есть integer.

Из написанной мной реализации можно смотреть что у меня более правильная реализация которая не нагружает бузу данных.

Всем спасибо. Учитесь

Edited June 24, 2011 by solovin1986

Int · June 24, 2011

solovin1986, ты считаешь нормальным конструкцию $array[1][2][3][4]['name']?

http://govnokod.ru/7026

Ты автор кода?

И опять же, в первом посте не сформирована задача. Что дальше будет происходить с этими данными? Если нужно будет искать цепочку родителей i-го элемента, то в твоём случае придётся проходить весь твой n-мерный массив в поисках i. Если ты так любишь рекурсию, то тебе это понравится. Как эта задача решается в случае двумерного массива, я показал (нужно только сделать цикл до достижения нулевого родителя).

Нагрузка на базу у всех одинакова - 'select *', так что не пиши ерудны.

И да, я тоже считаю, что NOT NULL не нужен, достаточно явно указать заполнение поля в функции добавления комментария.

Veseloff · June 24, 2011

По поводу NOT NULL это высказывание абсурд, так как при добавлении в базу оно автоматом будет 0 так как есть integer.
Из написанной мной реализации можно смотреть что у меня более правильная реализация которая не нагружает бузу данных.
Всем спасибо. Учитесь

Вот за такие высказывания я бы не только вас не взял на работу, а выгнал бы с собеседования пинками. Давайте разберёмся почему.

1. 0 (ноль) это не NULL. NULL — отдельный тип данных. То есть 0 — число, а NULL — отсутствие какого-либо значения вообще. Так что, если вы попытаетесь вставить туда пустое значение, то получите NULL. Чтобы по умолчанию вставаль ноль, надо делать DEFAULT 0.

2. И с какого это молота у вас быстрее, а? Как минимум, у меня задача выполняется за линейное время и запрос в БД идёт всего один.

Обоснуйте своё предположение.

solovin1986 · June 24, 2011

solovin1986, ты считаешь нормальным конструкцию $array[1][2][3][4]['name']?
http://govnokod.ru/7026
Ты автор кода?
И опять же, в первом посте не сформирована задача. Что дальше будет происходить с этими данными? Если нужно будет искать цепочку родителей i-го элемента, то в твоём случае придётся проходить весь твой n-мерный массив в поисках i.
Нагрузка на базу у всех одинакова - 'select *', так что не пиши ерудны.

Ну теперь давай будем на личности переходить. )

В принципе то что я написал используют много движков.

Может Вы уважаемый хотите сказать что они вот то что вы написали?

Может вы хотите сказать что Ваш уважаемый модератор дает в задании то что вы написали?

Если нет тогда зачем Вы это пишите будучи уважаемым человеком на этом форуме?

По поводу NOT NULL это высказывание абсурд, так как при добавлении в базу оно автоматом будет 0 так как есть integer.
Из написанной мной реализации можно смотреть что у меня более правильная реализация которая не нагружает бузу данных.
Всем спасибо. Учитесь
Вот за такие высказывания я бы не только вас не взял на работу, а выгнал бы с собеседования пинками. Давайте разберёмся почему.
1. 0 (ноль) это не NULL. NULL — отдельный тип данных. То есть 0 — число, а NULL — отсутствие какого-либо значения вообще. Так что, если вы попытаетесь вставить туда пустое значение, то получите NULL. Чтобы по умолчанию вставаль ноль, надо делать DEFAULT 0.
2. И с какого это молота у вас быстрее, а? Как минимум, у меня задача выполняется за линейное время и запрос в БД идёт всего один.
Обоснуйте своё предположение.

Удалите тему и забаните меня и будет Вам счастье.

Вы бы еще сказали что вам нужно сказать что id это автоинкремент. Для 110%

Veseloff · June 24, 2011

И да, я тоже считаю, что NOT NULL не нужен, достаточно явно указать заполнение поля в функции добавления комментария.

Вот тут поспорю. NOT NULL означает то, что не надо хранить метку, означающую NULL это или нет. Это немного сэкономит память (незначительно, но всё же ) а вот на выборках даст ускорение.

solovin1986 · June 24, 2011

Для тех кому интересно как из многомерного массива вывести option-ы для select


function  get_region_option($arr){
    GLOBAL $option, $nbsp;
    $nbsp .= ' ';
	foreach( $arr as $key => $value ){
		if( is_array($value) ){
			$option .= "<option value=\"$key\">$nbsp{$value['name']}</option>\r\n";
			get_region_option($value);
		}
	}
	$nbsp = substr($nbsp,0,-6);
	return  $option;
}

print_r( get_region_option($region_tree) );

Короче на роботу не берете :facepalmxd:

Все тему закрывайте, а то будем биться.

Edited June 24, 2011 by solovin1986

stars · June 24, 2011


————————————————————————————————
CREATE TABLE IF NOT EXISTS `comments` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `parent` int(11) DEFAULT NULL,
  `name` varchar(255) DEFAULT NULL,
  `comment` text,
  PRIMARY KEY (`id`)
) ENGINE=MyISAM  DEFAULT CHARSET=utf8 AUTO_INCREMENT=14 ;

INSERT INTO `comments` (`id`, `parent`, `name`, `comment`) VALUES
(4, 0, 'Вася', 'Вот мой первый комментарий'),
(5, 4, 'Федя', 'Отвечаю на первый комментарий'),
(6, 5, 'Вася', 'Отвечаю на ответ'),
(7, 5, 'Пётр', 'Я тоже отвечаю на ответ'),
(8, 7, 'Иван', 'А я отвечаю Петру'),
(9, 0, 'Игорь', 'А вот ещё коммент первого уровня'),
(10, 0, 'Тамара', 'Девушка врывается в тред!'),
(11, 10, 'Федя', 'Привет, Тамара!'),
(12, 11, 'Тамара', 'Привет, Фёдор'),
(13, 10, 'Иван', 'Привет, Тамара, я Иван. А тебя как зовут?');
————————————————————————————————
Необходимо написать скрипт, который из данных этой таблицы построит следующий массив
————————————————————————————————
Array
(
    [4] =>  Array
        (
            [id] =>  4
            [parent] =>  0
            [name] =>  Вася
            [comment] =>  Вот мой первый комментарий
            [children] =>  Array
                (
                    [5] =>  Array
                        (
                            [id] =>  5
                            [parent] =>  4
                            [name] =>  Федя
                            [comment] =>  Отвечаю на первый комментарий
                            [children] =>  Array
                                (
                                    [6] =>  Array
                                        (
                                            [id] =>  6
                                            [parent] =>  5
                                            [name] =>  Вася
                                            [comment] =>  Отвечаю на ответ
                                        )

                                    [7] =>  Array
                                        (
                                            [id] =>  7
                                            [parent] =>  5
                                            [name] =>  Пётр
                                            [comment] =>  Я тоже отвечаю на ответ
                                            [children] =>  Array
                                                (
                                                    [8] =>  Array
                                                        (
                                                            [id] =>  8
                                                            [parent] =>  7
                                                            [name] =>  Иван
                                                            [comment] =>  А я отвечаю Петру
                                                        )

                                                )

                                        )

                                )

                        )

                )

        )

    [9] =>  Array
        (
            [id] =>  9
            [parent] =>  0
            [name] =>  Игорь
            [comment] =>  А вот ещё коммент первого уровня
        )

    [10] =>  Array
        (
            [id] =>  10
            [parent] =>  0
            [name] =>  Тамара
            [comment] =>  Девушка врывается в тред!
            [children] =>  Array
                (
                    [11] =>  Array
                        (
                            [id] =>  11
                            [parent] =>  10
                            [name] =>  Федя
                            [comment] =>  Привет, Тамара!
                            [children] =>  Array
                                (
                                    [12] =>  Array
                                        (
                                            [id] =>  12
                                            [parent] =>  11
                                            [name] =>  Тамара
                                            [comment] =>  Привет, Фёдор
                                        )

                                )

                        )

                    [13] =>  Array
                        (
                            [id] =>  13
                            [parent] =>  10
                            [name] =>  Иван
                            [comment] =>  Привет, Тамара, я Иван. А тебя как зовут?
                        )

                )

        )

)

Частное решение конкретно поставленной задачи:

SELECT *, if(parent=0, id, if(parent=10, id, parent)) as parent2  FROM comments ORDER BY parent2, id

собственно собрать древо при данной выборке уже не составит труда...

Я конечно понимаю что Veseloff ставя задачу хочет видеть универсальное решение, но условие гласит "из данных этой таблицы построит следующий массив", отсюда следую не однозначные выводы в том числе и мое решение которое удовлетворяет условию

P.S. извините не удержался

Edited June 24, 2011 by stars

Int · June 24, 2011

Для тех кому интересно как из многомерного массива вывести option-ы для select

Ну я ж говорил, что без рекурсии не обойдётся. Совсем память не бережёшь. А как насчёт прохода в обратную сторону?

Если какие-то сайты это используют, это не значит, что они выбрали оптимальное решение.

Может быть мы просто сравним время выполнения обоих подходов на базе размером записей хотя бы в 1000 с вложенностью где-нибудь так до сотни? А то спорим вхолостую.

И мне как-то всё равно, что за задачу задал модератор, я отвечал на вопрос первого поста.

Sign In

Рекурсивный массив

Question

solovin1986

Link to comment

Share on other sites

34 answers to this question

Recommended Posts

Veseloff

Link to comment

Share on other sites

solovin1986

Link to comment

Share on other sites

Int

Link to comment

Share on other sites

Veseloff

Link to comment

Share on other sites

solovin1986

Link to comment

Share on other sites

Veseloff

Link to comment

Share on other sites

solovin1986

Link to comment

Share on other sites

stars

Link to comment

Share on other sites

Int

Link to comment

Share on other sites

Join the conversation

Обсуждения

Forums

Important Information