Рекурсивная функция

Я не знаю что реально нужно автору, но я писал пример судя из этого текста их мервого поста:

Функция должна искать своих "предков" до корневого(т.е. со значение родителя равного "0"), записывать в массив их idObject...

В нем написано найти предков потомка, а не наоборот. Если автор неверно поставил задачу, то тогда прошу прощения. А свой пример токо-что протестил, все работает. А вопрос оптимизации уже дело второе. Я бы делал таблицу связей, или настроил кеширование в мускуле и выделил под кеш запросов метров 300 RAM. И тогда было бы оптимальнее и быстрее слать запросы к БД чем работать с массивом в пару десятков тысяч элементов. А может еще и с мемкешем поигрался, вообще бы все летало.

EuGen

Сейчас пробую ваш код и по идее $rgResult[] должен иметь свой набор потомков для каждого пункта?
(Добавление)
egir
Вот я тоже уже подумываю в базе хранит весь путь.

Но опять при добавлении и редактировании пункта придется перезаписывать все. Вдруг пункт поменяет место положение.

Для того набора данных, что в примере с функцией, результат таков:

-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.

В случае дерева нужно переформировывать его в случае добавления, удаления элементов в случае изменения родителя элемента и т.д. Но это делается когда происходит одно из таких событий. У меня дерево формируется очень быстро, хотя записей в каталогах более 10000.

EuGen, спасибо, вижу что работает. У меня тоже самое.
Я пока еще ни как не могу уяснить саму работу рекурсивной функции...

Так а что именно непонятного?
Проходим по всем узлам, которые подчинены текущему и рекурсивно собираем данные.
Первая итерация когда id=0 (предполагается, что при id=0 у узла нет родителя, то есть он корневой)

-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.

И я о том же немногим ранее.
Массив не "множиться" с каждой итерацией, а передается по ссылке "&". И в памяти только увеличивающаяся строка результата и всего один массив.
По времени это быстрее чем куча запросов.
О каком путе идет речь? который href="/dfgh/fgh/fg/" ??? Вот эго и храните.
Даже если он изменится, то только для этой странички.
А чтобы вывести страничку делайте запрос WHERE link = '/dfgh/fgh/fg/'
иначе = 404...

-----
Шта? Репозиторий?

Я не за массив который собирается, а за массив который получается когда достаете все записи со всеми категориями. А потом с ним работаете. 1-е нужно все (в некоторых случаях) эелементы этого массива обойти. А обьемРАМ будет равен кол-ву обращений к скрипту, то-есть количеству копий скрипта. При больших посещениях и большому кол-ву записей в таблице категорий это смерть, а при малых все равно каким способом делать. Кстати в нагруженных проектах увеличивается нагрузка на БД, а не на скрипты, и делаются кластера серверов БД, чтобы быстрее работали. Вся статика выносится на отдельный сервер(сервера). Таким образом одна морда может обслуживать 10-ки тысяч хостов. Кластера БД обходятся дешевле, чем 10-ки серверов с мордами.

(Отредактировано автором: 25 Августа, 2011 - 12:54:51)

Но случаев для формирования 10к записей меню и подменю и подменю и подменю и т.д. я не встречал...
Даже представить если - это сам браузер повесится от такой разметки..
Того кто сделает такой вывод - убьют при первой встрече.
Поэтому "некоторого случая" даже и быть не может.

-----
Шта? Репозиторий?

Пример форум, на высоко посещаемом форуме 10000 тем это не так уж и много. Сначала выбираем эти темы запросом который Вы предлагали:

SELECT id,pid,name,idObject FROM tbl

ПОтом пихаем это все в массив и получаем массив и получаем как раз массив с 10000 и более элементов, а потом самое интересное, начинаем по нему обход, чтобы сформировать второй массив с 5-ти элементов. Я вот про это говорил, что не совсем оптимально. В таком случае лучше 5 запросов к БД.

а на форуме бывает вложенное МЕНЮ по ВСЕМ темам, и все это на одной странице???
Удивляете.
Да и у топикстартера не форум.

-----
Шта? Репозиторий?

Приемлемый уровень вложения - 3. Все, что больше - создает неудобство. В этом сомнений думаю возникать не должно. Если все же возникают - советую почитать что-нибудь о проектировании пользовательских интерфейсов (модное слово "юзабилити" - туда же)
В памяти нужно хранить только 1 экземпляр первоначального массива и один - древовидного. Расходы допустимые. С учетом того, что при любой сложности запрос будет всего один (а именно работа с СУБД есть краеугольный камень быстродействия современных веб-приложений) это самый оптимальный вариант.

-----
Есть в мире две бесконечные вещи - это Вселенная и человеческая глупость. Но насчет первой .. я не уверен.

Та тут не важно что бывает. Вы в запросе вытаскиваете ВСЕ КАТАЛОГИ (категории или что там):

SELECT id,pid,name,idObject FROM tbl

и не важно что бывает, а что нет. tbl в запросе это таблица категорий, каталогов или чего там. Вы достали ВСЕ ЗАПИСИ, а потом запихнули их в массив, а потом обходите массив с n-записей (или n-тысяч записей) и формируете второй с 5-ти (условно, может меньше или больше) элементов. Не ужели я так непонятно излагаю. А количество записей в таблице может быть какое угодно, это кол-во тем, категорий, каталогов и т.д.
Если устраивает ситуация при разработке, типа у меня не будет больше 300 тем, а если их вдруг окажется несколько тысяч, то можно и переписать, то тут проблем нет.
Мы себе такого позволить не можем в разработке, проект делается из расчета на высокую нагрузку, по этому в нашем случае ни мой, ни Ваши примеры решения задачи не подходят. Нужна таблица связей или настраивать КЕШ мускуля, но формирования дерева с обходом не приемлимо, слишком большие затраты RAM на каждую копию скрипта.

(Отредактировано автором: 25 Августа, 2011 - 14:20:11)

Покажите реальный пример для вывода меню с подкатегориями для такого кол-ва пунктов и я с вами соглашусь.

Я второй массив не формирую - я формирую готовую html-разметку проходя первый массив единожды, при необходимости подключаю шаблон и прогоняю через него.

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

То что я показал в примере это НЕ единственный способ о котором я знаю и везде его применяю. Это всего лишь пример.
Величина занимаемой памяти, да и то только в последней итерации (конкатенация результата), будет примерно равна двойному обьему начальных данных.
Давайте проведем эксперимент производительности по критериям:

1. время выполнения.
2. загрузка CPU.
3. объем занимаемой памяти.
4. количество запросов.

Ну скажем чтоб ни вам ни нам, не на ваших 10к и не на моих 300 а на 3к пунктов.

-----
Шта? Репозиторий?

[quote=DeepVarvar] Покажите реальный пример для вывода меню с подкатегориями для такого кол-ва пунктов и я с вами соглашусь.

Вот опять 25. Пример forum[dot]ag[dot]ru. Заходим смотрим, на форуме ВНИМАНИЕ: 97426 тем. Все темы хранятся в одной таблице `tbl`. Структура проста:

id | parent_id | title | и т.д.
1 0 t1
2 1 t2
97426 1 t97426

Тпереб при заходе в тему id=97426 нужно найти ее родителей. Вы делаете запрос:

$res = mysql_query("SELECT id,pid,name,idObject FROM tbl");

Достаете все 97426 записей (ПРОСТО ПОТОМУ ЧТО ОНИ НУЖНЫ ЧТОБЫ НАЙТИ ВСЕХ РОДИТЕЛЕЙ ЭЛЕМЕНТА). Потом делаете $array = mysql_featch_array($res) и ВУАЛЯ перед нами массив в 97426 элементов. А теперь давайте обойдем его в поисках родителей, и все равно что с ним мы будем делать, html формировать, массив или чтото еще. Посмотрите какая нагрузка на машину когда даже array_search() используется для массива с таким кол-ом элементов. И эта процедура происходить при каждом входе пользователя в тему форума. А если одновременно в темы зайдет 1000 пользователей и запустится 1000 копий скрипта? Как по мне ниче хорошого не получится.

Надеюсь хоть сейчас понятна моя мысль. Я не говорю что Ваш метод не работает, я говорю что при больших посещениях и большом кол-ве записей он не оптимален ровно на столько, насколько способ рекурсивного формирования массива с запросами в каждой рекурсии к БД. Хотя в Данном случае все равно сколько записей, рекурсий будет ровно столько, сколько родителей то-есть 1 - 5 (запросов).

(Отредактировано автором: 25 Августа, 2011 - 18:46:38)