алгоритм для получения событий из временного интервала

Question

У меня есть несколько временных интервалов с событиями, связанными с каждым интервалом.Я сохранил их в хэш-карте.

(0-1]: [a, b, c, d] # time interval from 0 - 1 have events [a, b, c, d]
(1-2]: [a, b] # time interval from 1 - 2 have events [a, b]
(2-3]: [b, c] # time interval from 2- 3 have events [b, c]

Если мой ввод равен 1,5, я знаю, что он находится между 1 и 2, поэтому я могу взять контейнер 1-2 в O (1).Есть ли другой способ хранения этих данных?Это неэффективно, так как я мог бы потенциально повторить много событий на одну корзину.Моя интуиция говорит, что это может быть сохранено в каком-то дереве, возможно, в дереве префиксов?Но я не могу сосредоточиться на этом.Тем не менее, все алгоритмы дерева имеют O (logn) поиск, так что я думаю, что они не будут столь же эффективны при запросах?

Answer 1

Вы можете использовать дерево интервалов, которое Википедия описывает как «древовидную структуру данных», которая «позволяет эффективно находить все интервалы, которые перекрываются с любым заданным интервалом или точкой» в O (log n + m ) время, где n - количество интервалов в дереве, а m - количество интервалов, найденных запросом.См. Подробности о том, как его реализовать.

Обратите внимание, что "интервалы" в дереве интервалов соответствуют тому, что вы описали как "события": a , b и т. Д. «Интервалы времени», на которые вы ссылаетесь (0–1 и т. Д.), Не нужны в подходе с интервальным деревом.

Однако все алгоритмы дерева имеют O (logn) поисков, так что я думаю, они не будут так эффективны при запросах?

log n меньше, чем вы думаете.Например, если n ≤ 10 ⁹ (имеется в виду, до одного миллиарда интервалов), то log n <30. Так что для большинства реальных проблем,Алгоритм O (log <em>n ) можно рассматривать как алгоритм O (1).

(Кроме того, если говорить о производительности, мы говорим «эффективный», а не «эффективный».)