Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 52
Малатца!
Выбрать любое поддерево можно нерекурсивно средствами SQL + временными таблицами.
Можно поподробней?
Особенно, в части поддерева, не рекурсивно.
Особенно, в части поддерева, не рекурсивно.
Алгоритм зовётся обходом графа (в нашем случае дерева) в ширину. Про «средствами SQL» сразу оговорюсь: не SQL'92.
Выглядит примерно так:
Выглядит примерно так:
Взять пустые очеpеди O1 и O2
Поместить коpень в очеpедь O1
while (Одна из очеpедей O1 и O2 не пуста) {
if ( O1 не является пустой ) {
Пусть p - узел, находящийся в голове очеpеди O1
Посетить веpшину p и удалить ее из O1
Поместить всех сыновей веpшины p в очеpедь O2, начиная со стаpшего сына.
}
else {
В качестве O1 взять непустую очеpедь O2
в качестве O2 взять пустую очеpедь O1
}
}
за что такая «нелюбовь» к рекурсии?
За что такая «нелюбовь» к MPTT?
Полгода назад я писал об этом же, но для PHP. Вот моя реализация сборки многоуровневого дерева и AL с одним запросом к БД — habrahabr.ru/blogs/algorithm/52666/
Да, кстати, у меня в алгоритме предусмотрен вариант что сперва может идти ребенок, а лишь потом родитель. Потому как в жизни все возможно. Буду благодарен, если ты сделаешь ссылку из подвала своей статью.
Я бы тоже был рад воткнуть ссылку на эту статью, но судя по всему из-за кармы "+2" — не могу редактировать (или я что-то не верно понял? нет ссылок на редактирование. по времени может?)
Я бы тоже был рад воткнуть ссылку на эту статью, но судя по всему из-за кармы "+2" — не могу редактировать (или я что-то не верно понял? нет ссылок на редактирование. по времени может?)
Вопрос в том, что у тебя получается хеш списков, а у меня уже один отсортированный список.
Можно чуть подробнее — не понял
Какая у тебя структура массива в результате обработки получается?
Еще можно смотреть в сторону баз, умеющих рекурсивные запросы (например postgresql 8.4)
Под рекурсивным запросом тут имеется в виду ясное дело не рекурсивный вызов запроса из кода, а запрос, содержащий рекурсию в себе.
Под рекурсивным запросом тут имеется в виду ясное дело не рекурсивный вызов запроса из кода, а запрос, содержащий рекурсию в себе.
Я лично делаю так: беру все комментарии к записи и записываю их во временный массив. После этого рекурсивно вывожу из массива, соответственно, больше не обращаюсь к базе.
Это наверное не круто, если комментариев мульён, но до 50 работает прекрасно. Больше — не пробовал просто.
Это наверное не круто, если комментариев мульён, но до 50 работает прекрасно. Больше — не пробовал просто.
LOL, Perl'исты боятся рекурсии как огня.
Во первых — не боимся, а она нам не нравится;
Во вторых — мы знаем, какие грабли могут быть при использовании рекурсий;
В третьих — мы стараемся делать приложения которые работают быстрее;
В четвертых — Perl тут не при чем, на нем только реализация алгоритма.
Во вторых — мы знаем, какие грабли могут быть при использовании рекурсий;
В третьих — мы стараемся делать приложения которые работают быстрее;
В четвертых — Perl тут не при чем, на нем только реализация алгоритма.
> Во первых — не боимся, а она нам не нравится;
И чем же она не нравится? Аргументы «хавает стек» не принимаются — все нормальные интерпретаторы умеют использовать кучу в таких случаях.
> Во вторых — мы знаем, какие грабли могут быть при использовании рекурсий;
Какие же?
> В третьих — мы стараемся делать приложения которые работают быстрее;
Абсолютно зря. Рулят профилировщики.
> В четвертых — Perl тут не при чем, на нем только реализация алгоритма.
Если говорим об *алгоритме* — то зачем приводить реализацию на Perl?
И чем же она не нравится? Аргументы «хавает стек» не принимаются — все нормальные интерпретаторы умеют использовать кучу в таких случаях.
> Во вторых — мы знаем, какие грабли могут быть при использовании рекурсий;
Какие же?
> В третьих — мы стараемся делать приложения которые работают быстрее;
Абсолютно зря. Рулят профилировщики.
> В четвертых — Perl тут не при чем, на нем только реализация алгоритма.
Если говорим об *алгоритме* — то зачем приводить реализацию на Perl?
Непонятно, почему вот это должно быть лучше рекурсии — по памяти? времени? Все эти создания/копирования/удаления списков против нашёл/добавил… А если кто-то боится переполнения стека, то он может сделать свой стек вместо системного в динамической памяти, какого ему нужно размера (высота дерева, понятно), и эмулировать рекурсию.
Ну вот, начался кодосрач.
Сколько говорить, что я в своих статьях не навязываю никому свою идею, а только предлагаю альтернативу.
Вы когда в ресторан приходите тоже официанту и повару канифолите мозги по поводу того, что они готовят блюда которые вам не нравятся и предлагают вам его в меню? Наверно нет, вы спокойно выбираете то, что вам по вкусу и кушаете на здоровье.
Сколько говорить, что я в своих статьях не навязываю никому свою идею, а только предлагаю альтернативу.
Вы когда в ресторан приходите тоже официанту и повару канифолите мозги по поводу того, что они готовят блюда которые вам не нравятся и предлагают вам его в меню? Наверно нет, вы спокойно выбираете то, что вам по вкусу и кушаете на здоровье.
во-первых: не надо обобщать, Perl'исты тут действительно ни при чём. Таким же образом рекурсивных алгоритмов избегают программисты любых языков, даже функиональных, это определяется стилем и подходом человека к программированию, тем более не везде рекурсивные аглоритмы — панацея.
во-вторых: написал бы phoinixrw рекурсивный алгоритм, сейчас же понабежали бы умники рассуждающие о скорости работы программы + затратах памяти + о переполнении стека и других нелицеприятных вещах…
в-третьих можешь написать рекурсивный алгоритм — валяй, выкладывай, а то языками молоть все горазды а как сделать что-то самому так сразу в кусты
во-вторых: написал бы phoinixrw рекурсивный алгоритм, сейчас же понабежали бы умники рассуждающие о скорости работы программы + затратах памяти + о переполнении стека и других нелицеприятных вещах…
в-третьих можешь написать рекурсивный алгоритм — валяй, выкладывай, а то языками молоть все горазды а как сделать что-то самому так сразу в кусты
Без претензии на оригинальность:
Без претензии на оригинальность:
1. Добавляем в таблицу поле, в котором хранится порядковый номер записи (не id) без учёта уровня вложенности. Т.е. n для родителя, n+m для детей;
2. SELECT * FROM tree ORDER BY n;
3. В цикле разбираем результат и строим дерево на стороне приложения.
1. Добавляем в таблицу поле, в котором хранится порядковый номер записи (не id) без учёта уровня вложенности. Т.е. n для родителя, n+m для детей;
2. SELECT * FROM tree ORDER BY n;
3. В цикле разбираем результат и строим дерево на стороне приложения.
остается только сравнить по скорости с рекурсивным способом :-)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Нерекурсивная выборка всего дерева Adjacency List