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

Question

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

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

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

Range {
    Date start
    Date end
}

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

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

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

В-Г-В-Г-В * * 1 015

Структура данных может выглядеть следующим образом:

Boundary {
    Date value
    Range prev
    Range next
}

Range {
    Boundary start
    Boundary end
}

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

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

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

Answer 1

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

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

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

Answer 2

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

RoomID
ReservationID
PreviousReservationID
NextReservationID
StartTimeDate
EndTimeDate
Priority
UserID

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

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

-Adam

Answer 3

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

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

Answer 4

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

(RoomId, StartTime)

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

(boundary not between colBoudaryA and colBoundaryB)

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

(startBoundary < endBoundary)

Answer 5

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

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 6

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

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

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

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

Answer 7

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

Answer 8

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

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