Поиск количества параллельных событий с учетом времени начала и окончания

Question

У меня массивный (~ 10) набор событий, характеризующийся временем начала и окончания. Учитывая какое-то время, я хочу найти, сколько на этих событиях продолжалось в то время.

Какая структура данных будет полезна в этой ситуации? Операции, в которых я должен быть быстрым:

1. Вставка новых событий, например, {start: 100000 milliseconds, end: 100010 milliseconds}.
2. Запрос количества одновременных событий за заданное время.

---

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

Answer 1

Вы ищете interval tree.

• Строительство: O(n log n), где n это число интервалов
• запроса: O(m+log n), где m это число результатов запроса и n это число интервалов
• Space: O(n)

Answer 2

Предположим, что у нас есть сортированный набор (например, balanced binary search tree или skip list) структура данных с N элементов. Кроме того, предположим, что отсортированный набор O (журнал N) Время поиска, O (журнал N) Время вставки, и O (N) использование пространства (это разумные предположения, см red-black tree, например).

Одна из возможностей состоит в том, чтобы иметь два отсортированных набора, bystart и byend, соответственно отсортированные по времени начала и конца событий.

Чтобы найти число событий, которые продолжаются во время t, спросите byend для первого интервала, конец которого время больше, чем t: O (журнал N) операции поиска. Вызвать время начала этого интервала left. Теперь задайте bystart для количества интервалов, время начала которых больше или равно left и меньше t. Это O (log N + M), где M - количество таких интервалов. Итак, общее время поиска - O (log N + M).

Вставка была O (log N) для отсортированных наборов, которые мы должны сделать один раз для каждого отсортированного набора. Это делает общее время для операции вставки O (log N).

Строительство этой структуры с нуля просто состоит из N операций вставки, так что общее время для строительства O (N войти N).

использование пространства O (N) для каждого отсортированного набора, таким образом, общее использование пространства O (N).

Резюме:

• Вставка: O (журнал N), где N это число интервалов
• Построить: O (N журнал N)
• Запрос: O (log N + M), где M - количество результатов
• Spac е: O (N)

Answer 3

Просто добавить другие ответы, в зависимости от продолжительности времени и зернистость желаемого, вы могли бы просто иметь массив счетчиков. Например, если продолжительность времени составляет 24 часа, а желаемая степень детализации - 1 миллисекунда, в массиве будет 86 400 000 ячеек. При использовании одного 4 байта int на ячейку (этого достаточно, чтобы удерживать 10^9), это будет меньше 700 МБ ОЗУ по сравнению с решениями на основе дерева, которые занимали бы по крайней мере (8 + 8 + 4 + 4) * 10^9 = 24 ГБ ОЗУ для двух указателей плюс два ints для каждого узла дерева (поскольку 32 бита адресной памяти недостаточны, вам потребуется 64 бита на указатель). Вы можете использовать swap, но это значительно замедлит некоторые запросы.

Вы также можете использовать это решение, если вы заботитесь только о последних 24 часах данных, например, используя массив в виде циклического буфера. Помимо ограничения по времени и детализации, другой недостаток заключается в том, что время вставки интервала пропорционально длине интервала, поэтому, если длина интервала неограничена, у вас могут быть проблемы. С другой стороны, запросы - это поиск по одному массиву.

Answer 4

(Удлинение ответы от tskuzzy и Snowball)

Сбалансированное бинарное дерево имеет смысл, за исключением того, что требования к памяти были бы чрезмерными для ваших наборов данных. A B-tree будет гораздо более эффективным с точки зрения памяти, хотя и более сложным, если вы не сможете использовать библиотеку.

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

Вставки и запросы должны принимать время O (log N).

Несколько комментариев:

• Пути вы сформулировали вопрос, вы заботитесь только о числа активных событий, не , которые событий были активны. Это означает, что вам не нужно отслеживать, какое время начала идет с каким конечным временем! Это также облегчает исключение термина «+ M» в запросах, приведенных в предыдущих ответах.

• Будьте осторожны с точной семантикой вашего запроса. В частности, событие считается активным в момент времени T, если оно начинается в момент времени T? Если он заканчивается в момент времени T? Ответы на эти вопросы влияют на то, используете ли вы < или < = в определенных местах.

• Do не использовать структуру данных «набора», потому что вы почти наверняка хотите разрешить и подсчитать дубликаты. То есть, более одного события могут начинаться и/или заканчиваться одновременно. Набор обычно игнорирует дубликаты. Вместо этого вы ищете «мультимножитель» (иногда называемый «сумкой»).

• Многие деревья двоичного поиска не поддерживают «количество элементов < T» запросов из коробки. Но эту функциональность легко добавить, сохранив размер на каждом узле.