Как найти, находится ли точка в пределах набора интервалов?

Question

Я ищу самый быстрый способ решить, находится ли точка в строке внутри подмножества этой строки. мне дают целую точку, и у меня также есть «список» или:

1. очки, представленные целым числом (3, 10, 1000 и т.д.)
2. интервалы, которые я представляю на 2 целые числа (2:10 - все целые числа от 2 до 10 включительно, 50:60 и т. д.)

В этом примере, если значение моей точки равно 5, тогда я возвращаю true, потому что он включен в интервал , то же самое для 55. Если моя точка равна 1000, я также возвращаю true, потому что она соответствует списку точек.

Я ищу быстрый способ (более быстрый, чем линейный), чтобы проверить это условие, НЕ ИСПОЛЬЗУЯ, КАСАЮЩИСЯ Целочисленного числа, что и возможные точки (т. Е. Для интервала 1: 1000 я не хочу вводить в действие 1000 целых чисел). Можно ли это сделать в логарифмическом времени?

Благодаря

редактировать: вы можете считать, что любое время, необходимое для предварительной обработки списка данных равно 0, потому что как только мои начальные интервалы перерабатываются мне нужно применить этот тест 10k точек

Answer 1

Хм, может быть, вы можете использовать интервал или дерево сегмента:

• http://en.wikipedia.org/wiki/Segment_tree
• http://en.wikipedia.org/wiki/Interval_tree

Answer 2

Сначала проверьте hash_map точек. Это простая проверка.

Затем просто закажите карту интервалов по первой координате, а затем найдите lower_bound точки.

Затем проверьте, содержатся ли вы в возвращаемом элементе. Если вы этого не сделаете, вы не в нем.

Answer 3

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

Есть ли ограничения на диапазон? Исходя из этого, вы можете, вероятно, придумать функцию хеширования для поиска в постоянное время. Но это зависит от того, как ваши ограничения.

Answer 4

Вы можете сделать это в сублинейное время. GIVEN структуру данных дерева (я бы рекомендовал B-дерево), если вы не считаете время, затраченное на сбор дерева (большинство деревьев принимают n log n или подобное время строить).

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

Answer 5

Вы можете использовать Bloom Filter, чтобы проверить точку и посмотреть, если это не в интервале, в линейном O (1) времени. Если он проходит этот тест, вы должны использовать другой метод, такой как бинарный поиск, чтобы определить, является ли он определенно частью интервала в O (log n) времени.

Answer 6

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

enum pointType { 
    point, 
    open, 
    close 
}; 
std::map<long int, pointType> mapPoints; 

mapPoints.insert(std::pair<long int, pointType>(3, point)); 

//create the 5:10 interval: 
mapPoints.insert(std::pair<long int, pointType>(5, open)); 
mapPoints.insert(std::pair<long int, pointType>(10, close)); 

int number = 4; 
bool inside = false; 
std::map<long int, pointType>::iterator it1 = mapPoints.lower_bound(number); 

if(it1->first == number || it1->second == close) { 
    inside = true; 
} 

Я думаю, что это должно работать до тех пор, как карта правильно заполнены не - интервалы перекрытия