Генерация древовидного меню модели представления Nested Sets

[Quiz]

Очередная тривиальная задача, решение которой гуглится ровно одну минуту.
Скажите, какая религия помешала воспользоваться классическим parent вместо избыточных level, left_key и right_key?

[rakot]

Отвечу за автора, это реализация Nested Set, довольно удобная штука если нужно вытягивать часть ветки целиком. А вообще да, задача тривиальная и parent тут больше подходит.

[jokagent]

Вообще говоря, такую структуру завели для хранения большого количества папок с последующей AJAX-подгрузкой с целью уменьшить нагрузку на БД.

[jokagent]

В моем конкретном случае, так удобнее задавать положение папки (выше-ниже), основываясь на значениях left key и right_key. А как вы предлагаете организовать сортировку «по-важности», как часто бывает у заказчиков?

[Goodkat]

как вы предлагаете организовать сортировку «по-важности», как часто бывает у заказчиков?

Дополнительным целочисленным полем «vazhnostj» в таблице, и сортировать по нему? :)

[maximw]

Предлагаю такую таблицу
id — идентификатор строки
parent — id родителя
caption — название каталога
order — число задающее порядок сортировки элементов.

Далее при рекурсивной отрисовке одного уровня делаем сортировку детей по важности. Ее можно сделать как средствами ЯП, так и СУБД, если делать для отрисовки детей каждого элемента отдельный запрос.

[Verkholantsev]

У меня два вопроса:

1. Почему вы используете for(... in ...) для итерирования массивов?
2. Почему вы не используете литералы для создания массивов и объектов?

[jokagent]

1. Осталась плохая привычка от итерирования объектов, надо искоренять.
2. Использовал сперва, но для пущей наглядности решил сделать как есть теперь.

[Verkholantsev]

Не совсем понимаю, что вы имеете в виду под пущей наглядностью. Дело в том, что использование литералов вместо конструкторов в JavaScript — это очень хорошая практика. Ваш код, например, может некорректно работать, если переопределить функцию Array(). Использование же литералов упасет вас от такой проблемы. К тому их использование соответствует принципу KISS.

[Anonym]

А чем плох for(... in ...) для массива?

[jokagent]

Плох тем, что итерация идет и не по числовым индексам тоже, а среди них обычно бывают совсем не элементы массива. В общем случае желательно использовать обычный for по длине массива, или forEach(нет поддержки IE). У jQuery также есть свои методы, к примеру тот же $.each()

[Anonym]

Всегда делал так for (var i in arr) if (arr.hasOwnProperty(i)) { ... } и не парился массив это или объект.
Думал может дело в скорости.

[Verkholantsev]

В качестве пояснений к ответу автора приложу вам ссылку на stackoverflow: stackoverflow.com/questions/500504/why-is-using-for-in-with-array-iteration-such-a-bad-idea

[jokagent]

Кстати, вот еще хорошая статья про сравнение скорости итерации различными методами

[Anonym]

Спасибо, это действительно многое объясняет. Буду знать.

[ComputerPers]

А почему бы всем дружно не добавить в комментарии свои варианты реализации?
Получится нормальный справочник по реализации конкретной задачи, с примерами, обсуждением и т.п.

P.S. Не девелопер.

[geakstr]

Oracle и Ruby.

В БД таблица с полями id, pid и другими. К ней выполняется иерархичный запрос вида

…
CONNECT BY PRIOR id = pid AND PRIOR pid <> PRIOR id START WITH pid = 0

(в последних версиях Oracle можно дописать NOCYCLE вместо второго условия) возвращающий level помимо прочих полей.

На основе запроса следующий код формирует HTML:

html = "<ul>\n"
prev_lvl = 1

DB.fetch(sql) do |row|
  cur_lvl = row[:lvl].to_i

  0.upto(prev_lvl - cur_lvl) { html += "</ul>\n" } if cur_lvl < prev_lvl

  html += "<ul>\n" if cur_lvl != prev_lvl

  html += "<li>#{row[:title]}\n"

  prev_lvl = cur_lvl
end

html += "</ul>"

[zayko]

> проверку каждого элемента массива по заданному элементу этого же массива

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

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

Вам нужно построить массив-индекс по полю parent_id

TREE — исходный массив
BOOST — массив-индекс

1) Один раз пробегаетесь TREE и для каждого элемента

for NODE in TREE
   BOOST[NODE.parent_id].push NODE

Теперь дочки для любого узла выбираются очень просто:

 BOOST[NODE.id] #=> массив вложенных

Готовое и весьма быстрое решение для больших деревьев в моей репе на гитхабе:

github.com/the-teacher/the_sortable_tree/blob/master/app/assets/javascripts/render_tree_helper.js.coffee#L29

Алгоритм настолько хорош, что прекрасно работает даже на ruby. Что уже само по себе является хорошим доказательством целесообразности подхода.

[jokagent]

В чем именно заключается

рекурсивный ад

?

[zayko]

— берем узел => перебираем массив для поиска дочерних элементов
— — берем дочерний 0, перебираем массив для поиска дочерних. Удаляем дочерние из исходного
— — — берем дочерний 0, перебираем массив для поиска дочерних. Удаляем дочерние из исходного
— — — берем дочерний 1, перебираем массив для поиска дочерних. Удаляем дочерние из исходного
— — — берем дочерний 2, перебираем массив для поиска дочерних. Удаляем дочерние из исходного
— — берем дочерний 1, перебираем массив для поиска дочерних. Удаляем дочерние из исходного
— — — берем дочерний 0, перебираем массив для поиска дочерних. Удаляем дочерние из исходного
— — — берем дочерний 1, перебираем массив для поиска дочерних. Удаляем дочерние из исходного
— — — берем дочерний 2, перебираем массив для поиска дочерних. Удаляем дочерние из исходного
— берем узел => перебираем массив для поиска дочерних элементов. Удаляем дочерние из исходного

Ваш алгоритм так работает?
При выборке дочерних проверяются условия на left, right?
Вы еще и перебираете исходный, что бы очистить его?

OMG! это и есть ад.

Попробуйте построить дерево из 16.000 элементов не на JS или на JS, но на слабой машине.

Вы пытаетесь оптимизировать

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

Но это

1) не очень эффективно
2) уничтожает исходный массив, который еще может пригодиться

Как бы не злословили в ваш адрес комментаторы, о том, что построить дерево — это очень просто и тривиально — никому не верьте, здесь тоже нужно пошевелить мозгами.

[jokagent]

Да, код работает именно так, спасибо за замечания, обязательно учту в дальнейшем. Скажите пожалуйста, как именно может понадобиться исходный массив? Просто склонировать и оставить жить его можно без проблем, но я не могу понять смысла в его существовании, по крайней мере в пределах этой задачи.

При выборке дочерних проверяются условия на left, right?

А ведь без этого никуда, чем предлагаете заменить?

1) не очень эффективно

Как по-вашему, увеличит ли эффективность кода удаление элемента из массива элемента сразу при выполнении условия

if (under && l_in && r_in) {childs.push(arr[i]); /*здесь что-то вроде delete arr[i]*/}

[zayko]

я не могу понять смысла в его существовании

Если дерево большое то имеет смысл, кроме его отрисовки сделать автокомплитер, который будет искать и подсказывать нужные элементы в нем. Так контент-менеджеру будет удобно работать с большим деревом. Он вводит первые буквы узла который ищет, и через автокомплитер выбирает нужный для редактирования элемент.

В этом случае удалять элементы дерева не следует.

ключи left и right требуются в основном для сортировки. А потому с этой задачей прекрасно справляется серверная часть при выборке из БД.

Как по-вашему, увеличит ли эффективность кода удаление элемента из массива элемента сразу при выполнении условия

Удаление элементов никакого существенного прироста не дает.

Еще раз повторюсь — вам нужен массив-индекс, который позволит выбирать дочерние элементы мгновенно и пачками для заданного узла.

По сути, вы получаете мега-прирост производительности за счет 2-х кратного увеличения памяти. Т.к. массив фактически копируется, но с другим порядком элементов.

В языках, где элементы массива не копируются, а на них создается ссылка — вообще сказка, даже 2-х кратного увеличения памяти нет.

с 2008 года я лично адекватного решения задачи отрисовки Nested Set не нашел, потому сделал сам. И судя по всему весьма успешно.

Внутри моего гема вы сможете найти и руби реализацию и JS (CoffeeScript) реализацию.

[jokagent]

Спасибо за разъяснения, очень познавательно. Вы оправдываете ваш ник на гитхабе)