Карта поиска значений для значений между пределами с перекрытием - PullRequest
Новая
       38

Карта поиска значений для значений между пределами с перекрытием

0 голосов
/ 02 апреля 2019

Я пытаюсь ускорить мой алгоритм с картой. В основном я ищу ссылку, потому что я не знаю, как погуглить мою проблему.

У меня есть определенные объекты для диапазона значений. Теперь мне нужно найти объект, который используется для этого значения. Пример: 

 x --->

|0 ---- object A ---- 100|                  |140 -- object D -- 200|
                 |80 -- object B -- 120|
         |50-object C-100|

Так что, если я хочу что-то сделать с x = 10, я хочу получить object A. Если у меня есть x = 90, я хочу получить object A, object B и object C.

В данный момент я провожу цикл по всем объектам и проверяю их пределы. Но есть порядок (очевидно) в x. Я почти уверен (или, по крайней мере, надеюсь) использовать этот порядок, чтобы ускорить мою реализацию. Что-то вроде карты поиска с перекрывающимися пределами.

Запрос значения x выполняется в числовой реализации. Он вызывается очень часто (между 10 000 и 10 000 000 раз в зависимости от точности, размера решетки моей задачи, размера реальной проблемы, ...).

PS: Когда я пытаюсь использовать Google, я только нахожу что-то о картах Google или обычных таблицах поиска. Если у вас есть что-то, что я могу гуглить, я тоже рад этому.

1 Ответ

1 голос
/ 02 апреля 2019

Вы ищете дерево интервалов . Они включают специализированный тип бинарных деревьев и гораздо более эффективны, чем традиционный линейный поиск, который потребует O (N) времени поиска. Интервал деревьев нужно только:

Для запросов требуется время O (log n + m), где n - общее количество интервалов, а m - количество сообщенных результатов. Конструкция требует O (n log n) времени, а хранилище требует O (n) места.

Поскольку это описано в стандартном учебнике по алгоритмам (Cormen, Leiserson, Rivest & Stein's " Введение в алгоритмы "), вы найдете множество примеров в Интернете, написанных на разных языках, вместе с CLRS. Версия, используемая в качестве эталонной реализации.

...