Структура данных для хранения диапазонов
Я задаюсь вопросом, знает ли кто-либо о структуре данных, которая эффективно обработала бы следующую ситуацию:
Структура данных должна сохранить несколько, возможно наложение, диапазоны переменной длины на некотором непрерывном масштабе времени.
Например, Вы могли бы добавить диапазоны
a:[0,3], b:[4,7], c:[0,9].Время вставки не должно быть особенно эффективным.
Извлечения взяли бы диапазон в качестве параметра и возвратили бы все диапазоны в наборе, которые накладываются с диапазоном, например:
Get(1,2)возвратил бы a и c.Get(6,7)возвратил бы b и c.Get(2,6)возвратил бы все три.Извлечения должны быть максимально эффективными.
2 ответа
Вы можете использовать двоичное дерево, в котором диапазоны хранятся в иерархии. Начиная с корневого узла, который представляет собой всеобъемлющий диапазон, разделенный его серединой, вы проверяете, принадлежит ли ваш диапазон, который вы пытаетесь вставить, левому поддиапазону, правому поддиапазону или обоим, и рекурсивно продолжаете в соответствующих подузлах, пока вы не достичь определенной глубины, на которой вы сохраните фактический диапазон.
Для поиска вы проверяете свой входной диапазон относительно левого и правого поддиапазонов верхнего узла и погружаетесь в те, которые перекрываются, повторяя, пока вы не достигнете фактических диапазонов, которые вы сохраняете.
Таким образом, поиск имеет логарифмическую сложность. Вам все равно придется управлять дубликатами при извлечении, поскольку некоторые диапазоны будут принадлежать нескольким узлам.
Одна из структур данных, которую вы могли бы использовать - это одномерное R-дерево. Они предназначены для работы с диапазонами и обеспечивают эффективный поиск. Вы также узнаете об Операторах Аллена; существует дюжина других отношений между временными интервалами, кроме простого "перекрытия".
На SO есть и другие вопросы, затрагивающие эту область, в том числе: