Как определить, находится ли точка в заданном интервале?

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

Points, represented by an integer ( 3, 10, 1000, etc) Intervals, that I represent by 2 integers ( 2:10 is all integers from 2 to 10 inluded, 50:60, etc)

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

Я ищу быстрый способ (быстрее, чем линейный) для проверки этого условия, БЕЗ необходимости создавать столько целых чисел, сколько есть возможных точек (т. Е. Для интервала 1: 1000 я не хочу создавать 1000 целых чисел). Можно ли это сделать за логарифмическое время?

Спасибо

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

 Freddy12 апр. 2012 г., 21:55
Они заказаны?
 lezebulon12 апр. 2012 г., 21:54
они могли бы, но я могу предварительно обработать свои данные так, чтобы они больше не обрабатывались, что не является проблемой по времени, потому что я использую те же наборы интервалов для обработки 10k баллов
 Almo12 апр. 2012 г., 21:52
Могут ли интервалы перекрываться? Я не знаю наверняка, имеет ли это значение, но кажется, что так и должно быть.
 Karl Bielefeldt12 апр. 2012 г., 22:29
Вам нужно знатьwhich интервалы, в которых находится точка, или просто в каком-либо из них или нет?
 lezebulon12 апр. 2012 г., 22:01
- & gt; проверить редактирование

Ответы на вопрос(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;
}

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

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

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

 12 апр. 2012 г., 22:26
Если некоторые диапазоны перекрываются, вы можете отсортировать их и свести перекрывающиеся в один диапазон.
 lezebulon12 апр. 2012 г., 21:59
Я думаю, что могу предположить, что диапазон составляет от 0 до 10 миллионов.
Решение Вопроса
 13 апр. 2012 г., 01:45
+1 за правильный ответ. Это хорошо изученная проблема вычислительной геометрии («1D колющий запрос»).

ДАЙТЕ древовидную структуру данных (я рекомендую B-дерево), если вы не подсчитываете время, затрачиваемое на построение дерева (для большинства деревьев требуется n log n или аналогичное время). ).

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

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

 12 апр. 2012 г., 22:24
@MatthiasVallentin, да, это так. Размер фильтра Блума зависит от количества установленных точек и вероятности ложных срабатываний, а не от возможного диапазона входных данных.
 12 апр. 2012 г., 22:13
Есть ли идея хэшировать каждую точку в интервале?
 12 апр. 2012 г., 23:30
Спасибо, теперь я понимаю вашу идею. Тем не менее, есть много вариантов, которые параметры фильтра Блума исправить изначально. Поскольку эта структура данных часто используется в условиях ограниченного пространства, общий подход состоит в том, чтобы предполагать фиксированный размер и устанавливать количество элементов для получения оптимального значенияkколичество хеш-функций. Не могли бы вы уточнить, что вы подразумеваете под "размером"? После создания размер (базового) фильтра Блума, как правило, больше не изменяется.
 12 апр. 2012 г., 23:42
@MatthiasVallentin, извините, мне было неясно. Что я хотел сказать, так это то, что после выбора количества точек и вероятности ложных срабатываний (и количества хэш-функций) можно рассчитать размер массивов фильтров. Дело в том, что этоnot зависит от диапазона входов.

Затем просто упорядочите карту интервалов по первой координате и найдите нижнюю границу точки.

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

 12 апр. 2012 г., 22:02
Кажется, в некоторых ответах есть предположения, что интервалы могут перекрываться. Вы контролируете структуру данных, которую используете для решения этой проблемы - она не нуждается в зависимости от внешнего или начального установленного интервала. Поэтому вам не следует хранить перекрывающиеся интервалы в целом - объединяйте их при вставке в карту. Всякий раз, когда приходится иметь дело с интервалами, это довольно стандартно.

Ваш ответ на вопрос