Есть такой класс — элемент в некоем дереве.

class element {

  collection<element*> children;
  collection<element*> visible_children;

  void visit_tree( std::function<void(element*)> visitor);
};

Нужно написать функцию visit_tree которая посещает детей ровно один раз для данного visitor.

Специфика: коллекция visible_children может содержать как элементы из children так и какие-то другие, в том числе и из глубины иерархии.

Как бы классическая имплементация использует hash_set для обнаружения факта посещения:

  void element::visit_tree( std::function<void(element*)> visitor) {
   
     std::hash_set<uint_ptr> visited; 

     std::function<void(element*)> worker = [&]( element* el) {
        if( visited.has( uint_ptr(el) ) )
           return; 
        visited.put(el);
        visitor(el);
        children.for_each(worker);  
        visible_children.for_each(worker);
     };
  }

Вопрос можно ли как-нибудь обойтись без этого hash_set ?
Я в принципе могу добавить скажем так uint поле в element для маркерных целей.

Проблема осложняется еще тем что visitor функтор в принипе тоже может запускать visit_tree для каких-то других своих целей.

Задача а приниципе сходная с GC mark-n-sweep ситуациями поэтому может кто-то видел более элегантное решение?

Здравствуйте, c-smile, Вы писали:


CS>Вопрос можно ли как-нибудь обойтись без этого hash_set ?
CS>Я в принципе могу добавить скажем так uint поле в element для маркерных целей.

Ну точно не hash_set — это тормоза на ровном месте.

CS>Проблема осложняется еще тем что visitor функтор в принипе тоже может запускать visit_tree для каких-то других своих целей.

Ну 640К uint должно хватить для чего угодно.
Только их потом придется бегать очищать же. Или у тебя обработка однократная?

А деревья меняются по ходу дела? Или создаются вначале и так и живут?
А то можно ведь параллельную структуру данных завести.

Можно ли каждому элементу присвоить номер (в процессе заполнения дерева)? Если да, то вместо hash_set можно использовать просто битовый vector и обращаться к нему по номеру элемента — чистить его очень быстро и легко.
Если у тебя flat tree (т.е. поверх массива) — то это вообще тривиально будет.

You will always get what you always got
  If you always do  what you always did

Здравствуйте, jazzer, Вы писали:

J>Здравствуйте, c-smile, Вы писали:


CS>>Вопрос можно ли как-нибудь обойтись без этого hash_set ?
CS>>Я в принципе могу добавить скажем так uint поле в element для маркерных целей.

J>Ну точно не hash_set — это тормоза на ровном месте.

CS>>Проблема осложняется еще тем что visitor функтор в принипе тоже может запускать visit_tree для каких-то других своих целей.

J>Ну 640К uint должно хватить для чего угодно.
J>Только их потом придется бегать очищать же. Или у тебя обработка однократная?

Обработка неоднократная. Я в принципе могу прикопать где-то некий mask, типа

static uint generation_mask = 1;

class element {

  uint visitor_mask;

  element() : visitor_mask(0) {}

  void element::visit_tree( std::function<void(element*)> visitor) {

     generation_mask <<= 1;

     // проверка на bit 0/1 ...

     std::function<void(element*)> worker = [&]( element* el) {
        if( (visitor_mask & generation_mask) != 0)        
           return; 
        visitor_mask ^= generation_mask; 
        visitor(el);
        children.for_each(worker);  
        visible_children.for_each(worker);
     };

     worker(this);
     
     generation_mask >>= 1;

  }
}

В этом случае глубина вложения visit_tree ограничена 32 что в принципе устраивает.


J>А деревья меняются по ходу дела? Или создаются вначале и так и живут?
J>А то можно ведь параллельную структуру данных завести.

Меняются.

J>Можно ли каждому элементу присвоить номер (в процессе заполнения дерева)? Если да, то вместо hash_set можно использовать просто битовый vector и обращаться к нему по номеру элемента — чистить его очень быстро и легко.
J>Если у тебя flat tree (т.е. поверх массива) — то это вообще тривиально будет.

Не понял что имеется ввиду. Поясни. Элементов много.

Здравствуйте, c-smile, Вы писали:

[]

J>>А деревья меняются по ходу дела? Или создаются вначале и так и живут?
J>>А то можно ведь параллельную структуру данных завести.

CS>Меняются.

J>>Можно ли каждому элементу присвоить номер (в процессе заполнения дерева)? Если да, то вместо hash_set можно использовать просто битовый vector и обращаться к нему по номеру элемента — чистить его очень быстро и легко.
J>>Если у тебя flat tree (т.е. поверх массива) — то это вообще тривиально будет.

CS>Не понял что имеется ввиду. Поясни. Элементов много.

Рискну влезть и предположить, что jazzer имел ввиду, что если все элементы дерева хранятся в одном массиве, а в children и visible_chidlren используются лишь указатели на элементы в этом массиве, то каждому элементу можно сопоставить индекс в массиве. В этом случае visited будет битовым вектором, и признак посещения элемента — это лишь бит по индексу элемента.

Мне кажется, если есть возможность элементам при создании в дереве присваивать возрастающие id = last_used_id++, то при незначительных изменениях в дереве (ну и при условии что элементы не перемещаются между деревьями) все элементы в нем будут иметь индексы от 0 до last_used_id и битовый вектор подойдет в качестве visited.

Здравствуйте, c-smile, Вы писали:

J>>Ну 640К uint должно хватить для чего угодно.
J>>Только их потом придется бегать очищать же. Или у тебя обработка однократная?

CS>Обработка неоднократная. Я в принципе могу прикопать где-то некий mask, типа
CS>В этом случае глубина вложения visit_tree ограничена 32 что в принципе устраивает.

Да, я именно это и имел в виду.

J>>А деревья меняются по ходу дела? Или создаются вначале и так и живут?
J>>А то можно ведь параллельную структуру данных завести.

CS>Меняются.

J>>Можно ли каждому элементу присвоить номер (в процессе заполнения дерева)? Если да, то вместо hash_set можно использовать просто битовый vector и обращаться к нему по номеру элемента — чистить его очень быстро и легко.

Если можно пронумеровать (при создании или отдельным проходом, если дерево редко перетряхивается) — то ты просто заводишь вектор флагов (или интов, если нужно считать количество заходов, или чего угодно еще) размера дерева, и потом в обработчике берешь id элемента и используешь его как индекс в массиве флагов. Рулез в том, что будет ровно одна аллокация и чистить (обнулять) можно банальным memset.
Плюс вектор можно заводить свой на каждый обработчик — код будет примерно такой же, как с hash_set, но гораздо дешевле, во всех смыслах (и скорость доступа, и использование памяти), плюс по нему потом можно быстро сделать агрегацию, если у тебя визитор агрегирующий.
Причем не беда, если в векторе будут дырки из-за того, что какие-то номера изчезли из дерева — тебе ведь для визитации нужно только на текущей номер смотреть: т.е. чистишь один раз, а дальше взводишь/проверяешь флаг.

J>>Если у тебя flat tree (т.е. поверх массива) — то это вообще тривиально будет.

CS>Не понял что имеется ввиду. Поясни. Элементов много.

flat_xxx — это ххх на массиве.
Например, http://www.boost.org/doc/libs/1_55_0/boost/container/detail/flat_tree.hpp (на нем реализованы бустовские flat_(multi)map/set: http://www.boost.org/doc/libs/1_55_0/doc/html/container/non_standard_containers.html#container.non_standard_containers.flat_xxx)

Соответственно если ты можешь реализовать свое дерево на массиве (например, через Boost.Intrusive), то номером элемента естественным образом становится номер ноды в массиве (просто разница указателей) — а дальше как выше, с вектором. Причем в этом случае ты сможешь прыгать из массива флагов в элемент дерева за один шаг — так как есть взаимно-однозначное соответствие между ними.

You will always get what you always got
  If you always do  what you always did

Здравствуйте, c-smile, Вы писали:

CS>Специфика: коллекция visible_children может содержать как элементы из children так и какие-то другие, в том числе и из глубины иерархии.

Казалось бы! Если множество children со всеми вложенными покрывает множество visible_children со всеми их вложенными, то достаточно пробежаться только по children.

Расскажи подробнее про порядок обхода.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, c-smile, Вы писали:

CS>>Специфика: коллекция visible_children может содержать как элементы из children так и какие-то другие, в том числе и из глубины иерархии.

К>Казалось бы! Если множество children со всеми вложенными покрывает множество visible_children со всеми их вложенными, то достаточно пробежаться только по children.

К>Расскажи подробнее про порядок обхода.

Врядли. Я так понял ситуацию:
children — это непосредственно дети элемента
visible_children — то что отображается — здесь отработают какие нибудь фильтры над children + дети могут приходить с нижних иерархий, например в каком нибудь случае уплощения дерева, когда детей с нижних иерархий надо передвинуть в рутовую ноду.

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

Здравствуйте, korzhik, Вы писали:

К>>Казалось бы! Если множество children со всеми вложенными покрывает множество visible_children со всеми их вложенными, то достаточно пробежаться только по children.

K>Врядли. Я так понял ситуацию:
K>children — это непосредственно дети элемента

Так я же сказал: "множество со всеми вложенными", т.е. дети детей и т.д.

K>visible_children — то что отображается — здесь отработают какие нибудь фильтры над children + дети могут приходить с нижних иерархий, например в каком нибудь случае уплощения дерева, когда детей с нижних иерархий надо передвинуть в рутовую ноду.

K>Если это так, то у меня в голове возникает пока такая простая мысль: пройтись по всем нодам и сохранить указатели на них, потом в полученном массиве удалить дупликаты и потом пустить по этому массиву визитор.


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

Либо это не дерево, а чёрт знает что.
Либо порядок обхода какой-нибудь хитрый вширь с опережениями, а не вглубь: например, оббежали непосредственных детей и видимых; затем спустились на уровень ниже и повторили процедуру (за вычетом ранее посещённых видимых).

Здравствуйте, jazzer, Вы писали:

J>Соответственно если ты можешь реализовать свое дерево на массиве (например, через Boost.Intrusive), то номером элемента естественным образом становится номер ноды в массиве (просто разница указателей) — а дальше как выше, с вектором. Причем в этом случае ты сможешь прыгать из массива флагов в элемент дерева за один шаг — так как есть взаимно-однозначное соответствие между ними.

Если нет необходимости заводить много разных флагов, причём заранее не известно сколько, то можно хранить эти флаги в самих узлах (которые лежат в массиве) — это может быть быстрее чем отдельный массив, так как меньше индерекций/random access.

С отдельным массивов флагов будет сначала random access в этот массив, а потом к самому элементу. Зато очистка флагов супер-быстрая, да и размер массива флагов намного меньше массива узлов.
С интрузивными флагами будет один random access (точнее для больших объектов могут быть загружены несколько последовательных cache line). Очистка будет медленней чем memset, но это всё же последовательный обход, пусть и с константными прыжками.

Вообще, если гарантированно обходятся все элементы, то очистка флагов необязательна — достаточно помнить какое значение флага в этот раз обозначает visited. При такой схеме можно с уверенностью сказать, что отдельный массив флагов будет медленней (за счёт лишних индерекций).

Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Здравствуйте, jazzer, Вы писали:

J>>Соответственно если ты можешь реализовать свое дерево на массиве (например, через Boost.Intrusive), то номером элемента естественным образом становится номер ноды в массиве (просто разница указателей) — а дальше как выше, с вектором. Причем в этом случае ты сможешь прыгать из массива флагов в элемент дерева за один шаг — так как есть взаимно-однозначное соответствие между ними.

EP>Если нет необходимости заводить много разных флагов, причём заранее не известно сколько, то можно хранить эти флаги в самих узлах (которые лежат в массиве) — это может быть быстрее чем отдельный массив, так как меньше индерекций/random access.

так это и обсуждалось же сначала

EP>С отдельным массивов флагов будет сначала random access в этот массив, а потом к самому элементу. Зато очистка флагов супер-быстрая, да и размер массива флагов намного меньше массива узлов.
EP>С интрузивными флагами будет один random access (точнее для больших объектов могут быть загружены несколько последовательных cache line). Очистка будет медленней чем memset, но это всё же последовательный обход, пусть и с константными прыжками.

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

EP>Вообще, если гарантированно обходятся все элементы, то очистка флагов необязательна — достаточно помнить какое значение флага в этот раз обозначает visited. При такой схеме можно с уверенностью сказать, что отдельный массив флагов будет медленней (за счёт лишних индерекций).

А если иметь flat tree и порядок обхода не важен — то можно вообще просто напрямую по массиву пройтись и забить на то, что это дерево

You will always get what you always got
  If you always do  what you always did

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, c-smile, Вы писали:

CS>>Специфика: коллекция visible_children может содержать как элементы из children так и какие-то другие, в том числе и из глубины иерархии.

К>Казалось бы! Если множество children со всеми вложенными покрывает множество visible_children со всеми их вложенными, то достаточно пробежаться только по children.

Это HTML DOM tree. children это то что описано в исходном HTML, visible_children это то что рендерится.

Пример, исходный markup:

<table>
  <tr><td>1</td></tr>
</table>

А вот rendering tree:

<table>
  <tbody>
    <tr><td>1</td></tr>
  </tbody>
</table>

В этом случае tbody создано искусственно. Т.е. rendering tree содержит элементы которых нет в children.

В другом случае какие-то элементы могут быть display:none — есть в children (C set) но их не будет в visible_children (V set)

К>Расскажи подробнее про порядок обхода.

Т.е. нужно обходить всегда и С и V — множество C ∪ V математически говоря.

Ибо в общем случае:

(C ⋂ V) ∉ C
(C ⋂ V) ∉ V

Здравствуйте, korzhik, Вы писали:


K>Врядли. Я так понял ситуацию:
K>children — это непосредственно дети элемента
K>visible_children — то что отображается — здесь отработают какие нибудь фильтры над children + дети могут приходить с нижних иерархий, например в каком нибудь случае уплощения дерева, когда детей с нижних иерархий надо передвинуть в рутовую ноду.

Да так и есть.

K>Если это так, то у меня в голове возникает пока такая простая мысль: пройтись по всем нодам и сохранить указатели на них, потом в полученном массиве удалить дупликаты и потом пустить по этому массиву визитор.

1. Построить массив.
2. Создать hash_set за для обнаружения дупликатов.

Это еще хуже чем мой начальный вариант. Там только hash_set.

Здравствуйте, jazzer, Вы писали:

J>А если иметь flat tree и порядок обхода не важен — то можно вообще просто напрямую по массиву пройтись и забить на то, что это дерево

Мой парсер завис на сочетании flat tree ...

Как я понимаю это вектор содержащий все элементы дерева от root.

А как это все планируется обходить если нужно обойти только под-дерево?
И как maintain этот массив? Дерево живое — постоянно меняется. Делать из него двусвязный список разве-что. Но это накладно во многих смыслах.

Здравствуйте, c-smile, Вы писали:

<>
А почему нужно обязательно тащить рядом две иерархии?
Нельзя ли сделать одну объединяющую — при этом каждый узел имеет пометку "оригинальный/домысленный" (tbody) и "видимый/невидимый".

Забег по оригинальным сводится к обходу вглубь всех узлов, но визитёр дёргается только на оригинальных.
Забег по видимым — к обходу вглубь с полным игнорированием невидимых.
Забег по всем — к обходу вглубь.

И не надо при этом париться синхронизацией двух деревьев.

Я не спрашиваю, зачем вообще хранить оригинальную структуру. Ну прочитали html, распарсили, домыслили до канонического вида... И всё, дальше работай себе с каноническим, со всей этой кучей tbody.

Здравствуйте, c-smile, Вы писали:

CS>Здравствуйте, jazzer, Вы писали:

J>>А если иметь flat tree и порядок обхода не важен — то можно вообще просто напрямую по массиву пройтись и забить на то, что это дерево

CS>Мой парсер завис на сочетании flat tree ...

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

CS>Как я понимаю это вектор содержащий все элементы дерева от root.

да. Вернее, не элементы, а узлы.

CS>А как это все планируется обходить если нужно обойти только под-дерево?
Ну у узла же есть ссылки на детей/родителей. Так что все чтоно так же.

CS>И как maintain этот массив? Дерево живое — постоянно меняется. Делать из него двусвязный список разве-что.
Зачем список? Дерево. Ты же можешь несколько ссылок (указателей, или вообще индексов в массиве, чтоб проще было растить вектор) в узле хранить — на родителя, на своего первого ребенка, на следующего своего брата (с тем же родителем)...

CS>Но это накладно во многих смыслах.

Ну тут, как и во многих таких случаях, однозначного ответа нет, все зависит от сценария использования.
Оно вот действительно постоянно меняется? Вот прям на каждый третий чих? Или максимум пара нодов там/сям вставится (типа твоего tbody)?
Надо смотреть на твои реальные сценарии и считать, какой вариант дороже выйдет.
Ты это все лучше нас знаешь, а нам маловато условий.

You will always get what you always got
  If you always do  what you always did

Здравствуйте, c-smile, Вы писали:

CS>Задача а приниципе сходная с GC mark-n-sweep ситуациями поэтому может кто-то видел более элегантное решение?

В итоге постулирую следуюшую лемму: задача в данной постановке (однократное сканирование) не
может быть решена с использованием переменных состояния сохраняемых в самих элементах/узлах.

Только с использованием внешнего storage т.е. это код ниже и его вариации есть единственный разумный способ.

 void element::visit_tree( std::function<void(element*)> visitor) {
   
     std::hash_set<uint_ptr> visited; 

     std::function<void(element*)> worker = [&]( element* el) {
        if( visited.has( uint_ptr(el) ) )
           return; 
        visited.put(el);
        visitor(el);
        children.for_each(worker);  
        visible_children.for_each(worker);
     };
  }

То же относится и графам содержащих циклы например.

Здравствуйте, c-smile, Вы писали:

CS>Здравствуйте, c-smile, Вы писали:

CS>>Задача а приниципе сходная с GC mark-n-sweep ситуациями поэтому может кто-то видел более элегантное решение?

CS>В итоге постулирую следуюшую лемму: задача в данной постановке (однократное сканирование) не
CS>может быть решена с использованием переменных состояния сохраняемых в самих элементах/узлах.

В смысле, это изменение требований?
В чем проблема добавить флажок/флажки в элементы?
Вон в Boost.Graph навешивают дополнительные данные на узлы только в путь.

CS>Только с использованием внешнего storage т.е. это код ниже и его вариации есть единственный разумный способ.

Тогда зависит от того, насколько часто и катастрофически перетряхивается дерево.
Потому что если нечасто или несильно — может, подойдет вариант с нумерацией и, соответственно, массивом вместо hash_set?

You will always get what you always got
  If you always do  what you always did

Здравствуйте, c-smile, Вы писали:

CS>В итоге постулирую следуюшую лемму: задача в данной постановке (однократное сканирование) не
CS>может быть решена с использованием переменных состояния сохраняемых в самих элементах/узлах.

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

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, c-smile, Вы писали:

CS>>В итоге постулирую следуюшую лемму: задача в данной постановке (однократное сканирование) не
CS>>может быть решена с использованием переменных состояния сохраняемых в самих элементах/узлах.

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

Этот алгоритм я и описал здесь:
http://rsdn.ru/forum/cpp.applied/5669052.1

Автор: c-smile
Дата: 01.07.14

Он работает в принципе, но только в случае если допускается двойной проход по дереву — второй раз нужно сбросить флаги элементов в исходное состояние.

Здравствуйте, jazzer, Вы писали:

J>Здравствуйте, c-smile, Вы писали:

CS>>Здравствуйте, c-smile, Вы писали:

CS>>>Задача а приниципе сходная с GC mark-n-sweep ситуациями поэтому может кто-то видел более элегантное решение?

CS>>В итоге постулирую следуюшую лемму: задача в данной постановке (однократное сканирование) не
CS>>может быть решена с использованием переменных состояния сохраняемых в самих элементах/узлах.

J>В смысле, это изменение требований?

Нет, требования не изменились.

J>В чем проблема добавить флажок/флажки в элементы?

Проблемы нет.

J>Вон в Boost.Graph навешивают дополнительные данные на узлы только в путь.

"навешивают дополнительные данные" именно для целей однократного обхода?

CS>>Только с использованием внешнего storage т.е. это код ниже и его вариации есть единственный разумный способ.

J>Тогда зависит от того, насколько часто и катастрофически перетряхивается дерево.

Практически любое изменение DOM на странице. В случае RSDN сайта это например открытие/закрытие узлов в дереве форумов.

J>Потому что если нечасто или несильно — может, подойдет вариант с нумерацией и, соответственно, массивом вместо hash_set?

Часто. И потом нумерация (сквозная) это тоже проход по дереву в общем случае.