Разработка структуры данных для упорядочивания событий

Question

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

• Тамявляется концепцией результата и серией событий, которые приводят к этому результату.
• События упорядочены в соответствии с порядком их появления, у них нет временных отметок, только позиция / индекс.
• Порядок событийне строгое.События могут происходить в другом порядке, как указано во входных данных.
• Существуют события, которые зависят от результатов других событий и это дает нам гарантию того, что их относительный порядок сохраняется.(Например: если у нас есть 4 события в этом порядке: A, B, C, D и события A & C являются зависимыми, тогда не может быть изменений в том, что C предшествует A).

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

пример:

- Event A<------+
- Event B <---+ | D2
- Event C <---|-|----+
- Event D ----+-+    |
- Event E <---|------+
- Event F ----+D1    |
- Event G -----------+ D3

• D1 описывает зависимость между F и B. F никогда не произойдет до B.
• D2 описывает зависимость между D и A. D никогда не произойдет до того, как A.
• D3 описываетзависимость между G и E и C. G никогда не произойдет раньше, чем E или C.

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

Для версии 2.0 мне понадобится возможный диапазон порядка текущего элемента, учитывая, что другие также могут двигаться.Т.е. в какой комбинации событие X находится как можно ближе к началу, или Y как можно ближе к концу.

Спасибо!

Answer 1

То, что вы описываете, может быть смоделировано с помощью направленного ациклического графа , в котором каждый узел представляет какое-то событие, ребро от u до v означает, что u должно идти раньше v.

Учитывая это представление, я считаю, что вы можете эффективно (за время O (n + m), где n - количество событий, а m - количество ограничений) определить самое позднее возможное время, когда какое-либо событие могло произойти, используя модифицированная топологическая сортировка . В частности, начните выполнять стандартную топологическую сортировку узлов, но всякий раз, когда вы будете расширять узел, представляющий рассматриваемое событие, вместо этого пропустите его и вместо этого разверните другие узлы (другими словами, выберите другой исходный узел). Когда вы полностью исчерпали другие узлы для расширения, у вас останется группа обеспечения доступности баз данных, в которой есть только один исходный узел, а именно узел, который вы хотите расширить. Таким образом, узлы, которые вы ранее расширили, являются событиями, которые потенциально могут произойти до того, как вам интересно, поэтому вы можете получить его последнюю возможную позицию, увидев, сколько событий предшествует этому.

В качестве оптимизации, если у вас есть фиксированная структура (вы не добавляете никаких событий или зависимостей), вы можете предварительно вычислить эту информацию, посчитав, сколько узлов-потомков имеет каждый узел в группе обеспечения доступности баз данных. Число потомков узла - это количество узлов, которые не могут быть расположены перед ним в любом топологически отсортированном порядке, и эта информация может быть вычислена один раз за время O (n + m). Как только вы кешируете это, последняя возможная позиция для каждого элемента будет n - 1 - k, где k - количество потомков этого узла.

Надеюсь, это поможет!