Хеширование диапазона

Question

У меня есть массив элементов диапазона. Каждый элемент имеет начало и конец. Внутри массива диапазоны не перекрываются и сортируются.

т.е. (код только для иллюстрации, не ожидайте его компиляции):

var arr = { [0,3], [5,10], [15,59] };

Учитывая значение (скажем, 9), есть ли хэш-функция диапазонов, которая позволит мне быстро получить элемент, имеющий диапазон, содержащий значение?

Конечно, есть наивное решение, просто переключайте каждый элемент, пока не найдете правильный; более сложный, такой как бинарный поиск по началу диапазона; и запатентованное создание двоичного дерева с диапазонами.

Но кто-нибудь знает, как использовать хеш?

Answer 1

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

Таким образом, это будет действительно быстро.

Answer 2

Как насчет использования Dictionary<int, Element> для хранения всех чисел во всех диапазонах, т.е. е. добавление четырех записей

0, [0,3]
1, [0,3]
2, [0,3]
3, [0,3]

и т. Д. Для других диапазонов. Он использует хэш с помощью словаря, но я сомневаюсь, что это наиболее эффективное решение.

Answer 3

Вы можете создать индекс для начальных значений для индексации в обр.

var arr = { [0,3], [5,10], [15,59] };

var dictStart = new Dictionary<int, int>();
dictStart.Add(0, 0);
dictStart.Add(5, 1);
dictStart.Add(15, 2);

Теперь, чтобы получить диапазон, вы можете выполнить двоичный поиск по значениям dictStart dict для первого элемента, который являетсявыше, чем значение для поиска.Затем возьмите предыдущую запись.

Трудно объяснить.В качестве примера посмотрите вверх 9. Выполните поиск того, что получило элемент e = [5, 1].

var range = arr[e[1]];   // = [5, 10]
bool isWithin = val <= range[1] && val >= range[0];

Таким образом, он будет менее инвазивным для памяти.Ключ заключается в быстром поиске начальных значений диапазонов.

Я думаю, это решит проблему, но это не хеш.