Допустим, есть N интервалов разной длины, полностью закрывающую некую допустимую область значений D.

Можно ли сделать хэш-функцию, которая по числу f из D скажет номер интервала за константное время?

Заранее благодарю!

Здравствуйте, RolandD, Вы писали:

RD>Допустим, есть N интервалов разной длины, полностью закрывающую некую допустимую область значений D.

RD>Можно ли сделать хэш-функцию, которая по числу f из D скажет номер интервала за константное время?

RD>Заранее благодарю!

Если область значений — целые числа и диапазон не слишком велик, то

Создаем массив a[min..max], прописываем a[i] = номер интервала.
Используем теперь f как индекс в этом массиве.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Используем теперь f как индекс в этом массиве.

Прошу прощения, забыл сказать — f вещественное число.

Здравствуйте, RolandD, Вы писали:

RD>Допустим, есть N интервалов разной длины, полностью закрывающую некую допустимую область значений D.

RD>Можно ли сделать хэш-функцию, которая по числу f из D скажет номер интервала за константное время?

RD>Заранее благодарю!

если нужен именно хеш, то можно смотреть в сторону фильтра Блума, но он не дает 100% точного ответа, да и в вашем случае вовсе неэффективен
тут проще было бы сделать дерево интервалов и проверять быстрее чем морочиться с подсчетом хеш функций

Здравствуйте, RolandD, Вы писали:

RD>Допустим, есть N интервалов разной длины, полностью закрывающую некую допустимую область значений D.
RD>Можно ли сделать хэш-функцию, которая по числу f из D скажет номер интервала за константное время?

Насколько я понимаю, задача сводится к поиску числа в отсортированном массиве из вещественных чисел.
При простейшем бинарном поиске сложность будет O(logN), что уже весьма неплохо.

В теории, можно попробовать привести число f к целому числу соответствующей разрядности и маской вырезать
из него наиболее значимые биты (знак, экспоненту и старшую часть мантиссы), на основе этих битов
сделать lookup-табличку, сужающую поиск до 1-2 интервалов в массиве.
Если интервалы будут разумной ширины — должно прокатить.

строим функцию которая имет следующи характеристики

строго возрастает. имеет на границах интервала целые значения совпадающие с номером интервала который начинается на этой границе.

вычисляем значение функции берем целую часть и вот результат.

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

правда бинарный поиск будет наверняка быстрее.

PD>Создаем массив a[min..max], прописываем a[i] = номер интервала.
PD>Используем теперь f как индекс в этом массиве.

А если интервал удалить надо?

Здравствуйте, LelicDsp, Вы писали:

LD>А если интервал удалить надо?

>есть N интервалов разной длины, полностью закрывающую некую допустимую область значений D

Если удалить — это станет неверным.

LD>>А если интервал удалить надо?

>>есть N интервалов разной длины, полностью закрывающую некую допустимую область значений D

PD>Если удалить — это станет неверным.
Почему? они же могут перекрываться

Здравствуйте, LelicDsp, Вы писали:


LD>Почему? они же могут перекрываться

Если они перекрываются, то как можно вообще вернуть номер интервала ? Их много может быть, номеров.

Здравствуйте, RolandD, Вы писали:

RD>Допустим, есть N интервалов разной длины, полностью закрывающую некую допустимую область значений D.
RD>Можно ли сделать хэш-функцию, которая по числу f из D скажет номер интервала за константное время?

Разбиваем D на M равных интервалов. Делаем хэш-таблицу на M слотов. Пусть Dmin, Dmax — нижня и верхняя границы D. Хэш функцией будет

H(f) = [(f - Dmin) / M]

Заносим в таблицу интервалы; понятно что большие попадут в несколько слотов, будет оверхед по памяти. M подбираем, исходя из допустимого количества коллизий. Можно даже анализировать конкретный набор интервалов перед построением, если на это есть время.