Какая лучшая структура данных для хранения диапазонов для быстрых запросов?

Question

У меня такая ситуация, когда у меня есть N временные рамки, каждая из которых содержит блоки. Блоки содержат токены с определенным индексом и знают их максимальные и минимальные индексы токенов. Кроме того, индексы сопоставляют первые индексы с парой (временной шкалой, блоком). Вот пример:

Timeline 1: [1 2 5 8 9 11] [14 17 18 21] [22 23 25 26] ... 
Timeline 2: [3 4 6 7 10 12] [13 15 16 19 20 24] [27 28 34 45] ... 

Index: 
    1 -> timeline 1, block 1 
    3 -> timeline 2, block 1 
    13 -> timeline 2, block 2 
    14 -> timeline 1, block 2 
    22 -> timeline 1, block 3 
    27 -> timeline 2, block 3 

Как вы можете видеть, отсутствует пропущенный токен (без пробелов).

Те структуры данных, что я изначально. Какова была бы лучшая альтернативная структура данных для оптимизации запросов определенного индекса токена? Скажем, я хочу получить токен 19. Теперь мне нужно сделать следующее: дихотомический поиск в индексе, чтобы найти хорошие блоки для каждой временной шкалы, а затем полный поиск в каждом блоке. С помощью маркера 19 дихотомический поиск приведет к блокам (1, 2) и (2, 2), которые могут содержать 19, а затем выполнить полный линейный поиск для поиска маркера 19 (здесь не существует дихотомического поиска внутри блоков, поскольку маркеры имеют различные размеры и пока не содержатся в какой-либо структуре данных).

Спасибо!

Редактировать: Я думаю об использовании дерева интервалов, содержащих интервалы всех временных рамок. Проблема в том, что запрос все равно приведет к множеству интервалов. Кроме того, он не оптимизирует слишком много по сравнению с бинарными поисками.

Answer 1

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

Answer 2

Самый простой способ (если он не занимает много места в памяти) заключается в создании массива значений blob, где index - ваш токен запроса (19 - в вашем примере), а значение - это blob которая ему соответствует. Массив должен быть хорошим, поскольку у вас нет пробелов. Построение этого массива - O (n) и поиск - O (1). Но это принесет определенные выгоды только в том случае, если количество запросов относительно велико, так как существующая структура также хорошо оптимизирована уже. (Если на самом деле тестирование здесь, какой путь быстрее.)

Построения массива:

array = [] 
foreach (timeline in timelines){ 
    foreach (block in timeline){ 
    foreach(token in block){ 
     array[token.index] = token.value 
    } 
    }  
} 

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

Answer 3

Возможно, вы можете использовать кривую заполнения разреженного пространства? Когда у вас есть индекс, это функция, которая уменьшает размерность. Кривая заполнения пространства такая же, но она также добавляет пространственную информацию к индексу. Другая структура данных для кривой заполнения пространства или пространственного индекса является квадрантом. Следовательно, вы можете использовать quadtree или kd-дерево для поиска.