Структура данных для неперекрывающихся диапазонов в одном измерении

Question

Мне нужна структура данных, которая может хранить непересекающиеся диапазоны в одном измерении. Весь диапазон измерения не должен быть полностью покрыт.

Примером может служить планировщик конференц-зала. Измерение - это время. Никакие два графика не могут пересекаться. Конференц-зал не всегда запланирован. Другими словами, для данного времени может быть не более одного графика.

Быстрое решение для диапазона, чтобы сохранить время начала и окончания.

Range {
    Date start
    Date end
}

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

Другая схема может включать сохранение одного граничного значения с каждым диапазоном. Но для непрерывной последовательности диапазонов всегда будет еще одно граничное значение, чем диапазоны. Чтобы обойти это, последовательность может быть представлена ​​в виде чередующихся граничных значений и диапазонов:

B = граничное значение, r = диапазон

BrBrB

Структура данных может выглядеть так:

Boundary {
    Date value
    Range prev
    Range next
}

Range {
    Boundary start
    Boundary end
}

По сути это двусвязный список с чередующимися типами.

В конечном итоге, любая структура данных, которую я использую, будет представлена ​​как в памяти (код приложения), так и в реляционной базе данных.

Мне любопытно, какие существуют академические или отраслевые решения.

Answer 1

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

2. Вы можете взглянуть на древовидную структуру Interval - для неперекрывающихся интервалов он имеет оптимальные операции запроса и изменения.

Answer 2

Если вам повезло (!) Использовать Postgres, вы можете использовать tstzrange столбец и применить ограничение для предотвращения наложений. Преимущество использования типа диапазона заключается в том, что он по своей сути предотвратит начало больше, чем финиш.

ALTER TABLE "booking" 
ADD CONSTRAINT "overlapping_bookings" 
EXCLUDE USING gist ("period" WITH &&, "room" WITH =);

Вам может понадобиться CREATE EXTENSION IF NOT EXISTS btree_gist, поскольку создание гистограммы с использованием && не поддерживается без этого расширения.

Answer 3

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

RoomID
ReservationID
PreviousReservationID
NextReservationID
StartTimeDate
EndTimeDate
приоритет
Идентификатор пользователя

Приоритет и идентификатор пользователя позволяют расписаниям иметь приоритеты (профессор может иметь больше влияния, чем группа студентов), так что новый элемент может "выбить" элементы с более низким приоритетом во время вставки, а идентификатор пользователя позволяет электронной почте быть отправили на встречу организаторам встречи.

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

-Адам

Answer 4

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

(RoomId, StartTime)

В случае непрерывных диапазонов вам обязательно нужно хранить 2 вещи, одну границу и либо вторую границу, либо длину. Обычно это делается путем сохранения второй границы, а затем создания ограничения на обе границы вида

(boundary not between colBoudaryA and colBoundaryB)

с дополнительным ограничением, которое

(startBoundary < endBoundary)

Answer 5

Это нетривиально, потому что (в мире баз данных) вам нужно сравнивать несколько строк, чтобы определить непересекающиеся диапазоны. Ясно, что когда информация находится в памяти, возможны другие представления, такие как списки во временном порядке. Тем не менее, я думаю, что вам лучше всего использовать нотацию "начало + конец", даже в списке.

Есть целые книги на эту тему - часть работы с "Временной базой данных". Два, на которые вы могли бы обратить внимание: Darwen, Date и Lorentzos " Временные данные и реляционная модель" и (в корне иной степени) " Разработка приложений базы данных, ориентированных на время, в SQL", Ричард Т. Снодграсс, Morgan Kaufmann Publishers, Inc., Сан-Франциско, июль 1999 года, 504+ XXII страницы, ISBN 1-55860-436-7. Это распечатано, но доступно в формате PDF на его веб-сайте cs.arizona.edu (так что поиск в Google делает его довольно легко найти).

Я полагаю, что одной из соответствующих структур данных является R-Tree. Это часто используется для двумерных структур, но также может быть эффективным для одномерных структур.

Вы также можете искать " Отношения Аллена" для интервалов - они могут быть полезны для вас.

Answer 6

Я имел успех, сохраняя время начала и продолжительность. Тест на перекрытие будет что-то вроде

WHERE NOT EXISTS (
   SELECT 1 FROM table
   WHERE BeginTime < NewBeginTime AND BeginTime + Duration > NewBeginTime
)
AND NOT EXISTS (
   SELECT 1 FROM table
   WHERE NewBeginTime < BeginTime AND NewBeginTime + NewDuration > BeginTime
)

Я думаю, без тестирования, но, надеюсь, вы получите дрейф

Answer 7

Многое зависит от того, что вы будете делать с данными, и, следовательно, какие операции должны быть эффективными. Тем не менее, я бы рассмотрел двусвязный список диапазонов с логикой в ​​установщиках Start и End, чтобы проверить, перекрывает ли он теперь своих соседей, и уменьшить их, если так (или сгенерировать исключение, или как вы хотите обработать попытку перекрытия).

Это дает хороший простой связанный список зарезервированных периодов для чтения, но нет контейнера, отвечающего за соблюдение правила отсутствия перекрытия.

Answer 8

Это называется ограничением "Унарный ресурс" в мире программирования с ограничениями. В этой области проводится много исследований, особенно для случая, когда время событий не фиксировано, и вам нужно найти временные интервалы для каждого из них. Существует коммерческий пакет C++, который решает вашу проблему, и больше Ilog CP, но он, вероятно, излишний. Существует также версия с открытым исходным кодом, которая называется eclipse (не имеет отношения к IDE).