Поиск временных данных

Question

Я разработал приложение (на C #), в котором объекты активны в течение определенного периода времени, они имеют свойства типа DateTime и относятся к ним. Теперь я хочу ускорить мою процедуру поиска для таких запросов, как: Есть ли другие активные объекты в этот период времени / в это время.

Существуют ли какие-либо временные индексы, которые я могу использовать или я могу использовать QuadTree / другие древовидные структуры для эффективного поиска.

Answer 1

Вам также следует взглянуть на дерево интервалов :

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

И это напоминает мне об этом ТАК вопрос .

Answer 2

Почему бы просто не упорядочить данные в списке, а затем использовать алгоритм поиска, подобный бинарному, чтобы ограничить число рассматриваемых объектов.

Answer 3

Имеется библиотека i4o (индексы для объектов). Может быть, это будет полезно.

Answer 4

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

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

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