Обновление вверх по дереву.

← →
Дмитрий С © (2012-12-19 03:31) [0]

Есть дерево представленное в виде id parent_id
У каждого элемента есть битовое поле flags (INT).
Изначально битовое поле заполнено только для листьев деревьев. Необходимо, чтобы все остальные ветки получили значение flags равное OR-сумме всех своих дочерних элементов.

Иначе говоря, нужно получить такое дерево, что, если у какого то элемента установлен, например, бит 3 (flags&4>0), то это значит, что какого-то его дочерего элемента или под-элемента или под-под-элемента имеется этот флаг.

Вопрос такой: как наиболее оптимально распространить эту информацию по дереву?

БД mysql.

← →
O'ShinW © (2012-12-19 08:53) [1]

На будущее триггер/хранимку на вставку/удаление

А сейчас.. предлагаю тупо(все равно - разово). Не зная MySQL, тока алго
1. Выбрать distinct родителей, у которых есть дети с битом
2 Поставить бит родителям.
Теперь принимаем их за листья и повторяем сначала.

← →
Ega23 © (2012-12-19 09:18) [2]

что-то типа:

procedure Foo(Node) begin for i := 0 to Node.ChildCount - 1 do Foo(Node[i]); Node.Parent.Flag := Node.Parent.Flag or Node.Flag; end;

← →
Медвежонок Пятачок © (2012-12-19 09:23) [3]

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

← →
Дмитрий С © (2012-12-19 11:49) [4]

> а если дерево перевести в нормальный формат имя которого
> нельзя называть

nested sets чтоли?)

← →
Ega23 © (2012-12-19 12:54) [5]

> nested sets чтоли?)

Нет, он за хмл

← →
Kerk © (2012-12-19 12:57) [6]

> Ega23 © (19.12.12 12:54) [5]
>
> > nested sets чтоли?)
>
> Нет, он за хмл

Остро! :)

← →
O'ShinW © (2012-12-19 13:01) [7]

> Остро! :)

не, имхо, то и имелось ввиду изначально :)

← →
Медвежонок Пятачок © (2012-12-19 13:02) [8]

Остро не остро, но я бы не не спрашивал как проапдейтить паренты по данным чайлдов. Мне бы этого просто не понадобилось.

← →
Медвежонок Пятачок © (2012-12-19 13:06) [9]

Вопрос такой: как наиболее оптимально распространить эту информацию по дереву?

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

Поэтому ты хочешь проапдейтить флагами сами паренты.

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

← →
Дмитрий С © (2012-12-19 13:48) [10]

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

Ну такое получилось, что сделаешь.

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

Написал пока такую хранимку, вызывается при загрузке или удалении файлов:
UPDATE `page` SET `contains` = (IF(`type`="file" AND `file_mime` LIKE "image/%", 1, 0) | IF(`type`="file" AND `file_mime` LIKE "video/%", 2, 0)), `contains` = IF(`contains` > 0, `contains` | 1073741824, 0); label1: LOOP UPDATE `page`, (SELECT parent_id, BIT_OR(contains) `bor` FROM page WHERE `contains`&1073741824=1073741824 GROUP BY parent_id) x SET `contains` = x.bor | 2147483648 WHERE x.parent_id = `page`.id; UPDATE `page` SET `contains` = IF(`contains`&2147483648=2147483648, (`contains`&~2147483648)|1073741824, `contains`&~1073741824) WHERE `contains`&(1073741824|2147483648) > 0; IF (ROW_COUNT() = 0) THEN LEAVE label1; END IF; END LOOP label1;
Магические числа: 2^30 и 2^31

← →
Kerk © (2012-12-19 13:50) [11]

Неправильная логика. Эту информацию из реляционной БД можно достать одним простым запросом. "Долго и дорого" оно только тогда, когда данных становится очень много. А в этом случае твой любимый XML просто не конкурентоспособен. Это даже если не вспоминать, что задача топикстартера - это не единственное, что обычно стоит перед БД.

← →
Медвежонок Пятачок © (2012-12-19 13:51) [12]

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

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

← →
O'ShinW © (2012-12-19 14:24) [13]

Kerk © (19.12.12 13:50) [11]
согласен.

Ну а если данных очень много и если нужна скорость на выборку - можно таблицу вести так, где хранить все связи вообще, с избытком
id pid lvl text
где lvl=0 - непосредственный парент
1 - внук, 2 - правнук и т.п.
поддерживать такую таблицу из триггеров/хранимок не очень сложно, а скорость будет хорошая.
Да и на вставку не думаю что очень много накладных расходов

← →
Медвежонок Пятачок © (2012-12-19 14:29) [14]

При чем здесь триггеры-шмиггеры? При чем здесь реляционные средства?

Я говорю про хранение дерева в памяти.

Впрочем о чем это я.
Лучше засеку сколько времени ветка будет актуальна для автора.

← →
БарЛог © (2012-12-19 14:34) [15]

По всей длине. От корней до самых кончиков (с) Реклама

← →
O'ShinW © (2012-12-19 14:46) [16]

> Медвежонок Пятачок © (19.12.12 14:29) [14]

да все хорошо с твоим xml :)
Куча квалифицированного народу село и написало удобные/отлаженные методы борьбы с ним. Зашибись. Реально.

Но т.к. это все же суть текст (и универсальный формат),
для конкретного частного случая может стоит поискать более оптимальную форму/методы?

← →
знайка (2012-12-19 14:50) [17]

> про хранение дерева в памяти.
Это когда все дерево загрузили, а если нет?

← →
Медвежонок Пятачок © (2012-12-19 15:05) [18]

для конкретного частного случая может стоит поискать более оптимальную форму/методы?

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

> про хранение дерева в памяти.
Это когда все дерево загрузили, а если нет?

А если нет, то отображение инфы будет неполным.
А у тебя по другому?
Данные не получил, но сумел отобразить?

← →
знайка (2012-12-19 15:07) [19]

> Данные не получил, но сумел отобразить?
Догрузил по мере прохода по дереву.

← →
Медвежонок Пятачок © (2012-12-19 15:10) [20]

И в чем тогда претензия?

← →
Jeer © (2012-12-19 15:54) [21]

К xml :)
Я удаляю все появляющиеся на винтах *.xml.
Радикально.

← →
Медвежонок Пятачок © (2012-12-19 16:26) [22]

Я слышал, что после этого надо еще святой водой винт окропить. Иначе не действует. Демоны того, кого нельзя называть, все равно достают программиста.

← →
картман © (2012-12-19 16:32) [23]

> Медвежонок Пятачок © (19.12.12 13:06) [9]

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

прошу прощения, а в XML - недорого и просто узнать содержимое чайлдов?

← →
Медвежонок Пятачок © (2012-12-19 16:37) [24]

прошу прощения, а в XML - недорого и просто узнать содержимое чайлдов?

Конечно.
А для тебя лично - узнаю вообще бесплатно

← →
картман © (2012-12-19 16:50) [25]

еще вопрос, пожалуйста: где расположена XML-ляндия? Где можно посмотреть герб, послушать гимн и ознакомиться с конституцией?

← →
знайка (2012-12-19 17:49) [26]

> И в чем тогда претензия?
Нет никаких претензий, как можно..
Вопрос только в том, как повлиет на решение, в данном случае, то, держим в памяти xml или что-то другое?
А при небольших деревъях, простой проход не такой уж и дорогой.
В любом случае, лучше если база сразу даст необходимую инфу, при малых затратах.
Юзать тут xml неоправдано, с моей т.з., если-бы еще оно в базе xml-ем лежало и то...

← →
Медвежонок Пятачок © (2012-12-19 19:27) [27]

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

← →
Дмитрий С © (2012-12-19 19:48) [28]

> Медвежонок Пятачок © (19.12.12 19:27) [27]

Что ты называешь нормальным?

Ты хочешь поговорить об этом?
А как же апдейт парентов?
Подождет?

Я тебе скажу что я считаю не нормальным.
Ты придумал структуру хранения.
Сам придумал.
Структура не дает тебе ответа на твой вопрос.
Не отвечает требованиям решаемой задачи.
И вместо того, чтобы использовать структуру, которая помогает решать задачу, ты ищешь способы подпереть свою структуру костылями, которые помогут решить задачу.

Вот это я и называю ненормальным.

> Медвежонок Пятачок © (19.12.12 19:56) [30]

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

Бла бла бла.....

PS днем я засек время, за которое будет решена эта детсадовская проблема.
К завтрему-то управишься?

Медвежонок Пятачок © (19.12.12 13:06) [9]

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

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

а кто с этим спорит?
никто.
А он вместо того, что бы конкретно спорить со мной по проблеме, начинает наматывать сопли на кулак. Ну как же, это же МП посоветовал, а все против него.

У него конкретная проблема:
Имея парента он не знает, лежит ли в чайлдах видос.
Я ему конкретно сказал, что если дерево будет в xml, то по паренту это можно легко и просто узнать.

Вот и все.
Но нет же. Он философствовать предпочитает.

> Бла бла бла.....
>
> PS днем я засек время, за которое будет решена эта детсадовская
> проблема.
> К завтрему-то управишься?

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

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

> Ну как же, это же МП посоветовал, а все против него.
>

Да у тебя мания величия.

Это не мания.
Посчитай на пальцах кто здесь поддержал меня.
Трепачок.

> Медвежонок Пятачок © (19.12.12 20:26) [38]

Ну, а ты сам то понимаешь что хрень предлагаешь? (речь как я понял о XML).

Я решение выложил, до того как ты свое время засек.

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

Обновление вверх по дереву. Найти похожие ветки