Древовидные очереди

Question

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

Я предполагаю, что это может работать примерно так: структура представляет собой дерево с одним корнем. Вы получаете своего рода «insert_iterator» в корень и затем помещаете на него элементы (например, a и b в примере ниже). Однако в любой момент вы можете также разделить итератор на несколько итераторов, эффективно создавая ветви. Ветви не могут снова слиться в одну очередь, но вы можете начать выталкивать элементы с начала очереди (опять же, используя своего рода visitor_iterator), пока пустые ветви не будут отброшены (на ваше усмотрение).

            x -> y -> z
a -> b -> { g -> h -> i -> j }
            f -> b

Есть идеи? Похоже на относительно простую структуру для реализации себя с помощью пула очередей, но я придерживаюсь стратегии «сначала подумай, потом код»:)

Спасибо

РЕДАКТИРОВАТЬ: Я думал, что я хотел бы добавить дополнительную справочную информацию. Это не относится к проблеме, но я подумал, что это может помочь прояснить мои цели. Очень грубо идея этой структуры состоит в том, что она в основном используется для планирования вычислений ... Ветвь может заканчиваться либо COMMIT, либо ROLLBACK. Если любой из x -> ..., g -> ... или f -> ... заканчивается COMMIT, то

a -> b

выполняется последовательно, а также ветвь, которая завершилась в COMMIT. Э.Г.

x -> y -> z -> COMMIT

Однако a -> b будет выполняться только один раз, когда хотя бы одна из ветвей зафиксирована. Если все три ветви заканчиваются ROLLBACK, тогда все дерево отбрасывается, включая начальные события a -> b.

Спасибо за великолепные ответы! Я подробно рассмотрю их, как только вернусь домой.

Answer 1

Библиотека Boost Graph содержит структуру данных, называемую непересекающимся набором, который моделирует необходимую вам структуру (взаимосвязанная группа наборов).

Еще один способ думать об этой структуре данных - это лес. Лес - это несвязный союз деревьев.

Answer 2

Вы говорите,

x -> y -> z -> COMMIT

, и это также может относиться к древовидной очереди, которая включает в себя несколькоN of y, набор проверок состояния / данных и выполняется сверху (z), но получает изменения состояния снизу (x).

x[N]("data check") -> x[N-1]("data check") -> x[N-2]("data

check ") -> check -> y-> check -> y-> state -> z -> check -> z-> state -> z-> commit.

кажется трудно поддерживать эту структуру, если очередьзакодирован от меньших к большим задачам, от x до z, но в конце концов, вы реализовали это именно таким образом?

Для меня (мой похожий вопрос Что такое шаблоны / типы очередей задач?Может ли многоуровневая очередь задач существовать в форме N-дерева? ) представляется структурой N-уровня, которая пересекает дочерние узлы с тремя типами конечных автоматов, доступных на каждом уровне:, $ me-> tryCommit(tryAdvanceChildsBelow (tryAdvanceToNextSiblingStep (getNextSibling ())) и грязная реализация, которая будет переписана.

Answer 3

K, я довольно серьезно посмотрел на все приведенные ответы, особенно на ускоренную реализацию непересекающегося множества, предложенную Quicksilver. (Нашли некоторые дополнительные ссылки здесь: http://en.wikipedia.org/wiki/Disjoint-set_data_structure и здесь: http://www.boost.org/doc/libs/1_42_0/libs/disjoint_sets/disjoint_sets.html).

Однако я пришел к выводу, что, хотя моя структура данных действительно является деревом, как подсказывают другие, алгоритмические требования к структуре намного лучше соответствуют требованиям очереди. Основные операции, которые я буду использовать, это push_front и pop_back, в то время как мне не нужны поиск, слияние и тому подобное. Следовательно, я чувствую, что пул очередей с определенным над ними «деревом индексации» в этом случае послужит мне лучше.

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

Так что сейчас я предпочитаю простую идею пула очередей. Как только новая очередь необходима, выберите ее из пула или создайте новую, если ее нет, а затем добавьте ее в дерево. Если очередь пуста, верните ее в пул и удалите узел дерева. Сам пул будет приоритетной очередью с самыми большими выделенными буферами спереди и самыми маленькими сзади. Через некоторое время будет выделено мало или вообще не будет новой памяти (при условии, что количество «выталкивания» более или менее совпадает с количеством «выталкивания»;))

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

Answer 4

Для меня это больше похоже на дерево (общее, а не двоичное), чем на очередь.Тем не менее, семантика удаления узла должна быть четко определена.

Кстати, упоминание "очереди планирования" звонит в звонок для Приоритетной очереди .

Answer 5

Мне кажется, что структура есть a Дерево , но не сбалансированный или двоичный вид. Если вы хотите получить полный контроль над тем, как добавляются новые узлы, вам придется указать, как это делается, например, a.addSibling(b).

Поскольку это для планирования, я предполагаю, что братьев и сестер нужно посещать примерно в одно и то же время. Ваш посетитель, вместо того, чтобы возвращаться назад, должен будет порождать других посетителей, где у вас есть ветвление. Таким образом, третий элемент для pop будет x, g и f.

Это может помочь вам взглянуть на JGraphT .