У меня есть набор временных интервалов In = (an, bn). Мне нужно запустить множество поисковых запросов, где мне предоставляется время t, и вам нужно быстро вернуть интервалы, которые содержат t, например, такие интервалы, что <= t <= bn.
Какова хорошая структура данных или алгоритм для этого?
Если это имеет значение, в моем случае an и bn являются целыми числами.
Что вы ищете, это Дерево интервала (это тип Дерево диапазонов).
Они имеют логарифмическое время поиска, как и другие древовидные структуры (например, деревья RB), поэтому вы должны увидеть сравнимую производительность с использованием чего-то вроде Java TreeMap или STL-карты.
Это вопрос о разделении пространства. У вас есть большое пространство с контейнерами и конкретная точка в этом пространстве, в каких контейнерах это касается? Многие игры должны решить эту проблему, поэтому неплохо было бы начать там. Посмотрите статьи о "широкомасштабном обнаружении столкновений".
Самый простой способ сделать это - разделить ваше числовое пространство на постоянное количество штук. Каждая часть знает, какие наборы пересекаются с ней, что-то, что вы вычисляете всякий раз, когда добавляется новый набор. Теперь, вместо того, чтобы тестировать каждый отдельный набор, когда у вас есть точка, вам нужно только проверить наборы, содержащиеся в части, в которой находится точка.
Другим общим и эффективным алгоритмом является Binary Space Partioning. Этот алгоритм подразделяет ваше пространство на две части. Каждая сторона знала, какие наборы пересекаются с ней. Вы можете рекурсивно повторить этот процесс до нужной вам точности (хотя не имеет смысла когда-либо создавать подразделение, меньшее, чем диапазон вашего самого маленького набора).
Вы можете проверить реализацию С#, которую я опубликовал в CodePlex для IntervalTree, которая точно решает эту проблему.
идо.
Ваша проблема только в одном измерении, поэтому она немного проще, чем проблемы разбиения пространства, встречающиеся в большинстве игр. У вас может быть только простой BST и в каждом листе помните список интервалов слева от листа.
если у вас были интервалы A (0, 10) и B (5, 15), тогда листья дерева были бы (0 с пустым списком), (5 с A), (10 с A, B) и (15 с B).