Здравствуйте, RolandD, Вы писали:
RD>Допустим, есть N интервалов разной длины, полностью закрывающую некую допустимую область значений D. RD>Можно ли сделать хэш-функцию, которая по числу f из D скажет номер интервала за константное время?
Насколько я понимаю, задача сводится к поиску числа в отсортированном массиве из вещественных чисел.
При простейшем бинарном поиске сложность будет O(logN), что уже весьма неплохо.
В теории, можно попробовать привести число f к целому числу соответствующей разрядности и маской вырезать
из него наиболее значимые биты (знак, экспоненту и старшую часть мантиссы), на основе этих битов
сделать lookup-табличку, сужающую поиск до 1-2 интервалов в массиве.
Если интервалы будут разумной ширины — должно прокатить.
Здравствуйте, RolandD, Вы писали:
RD>Допустим, есть N интервалов разной длины, полностью закрывающую некую допустимую область значений D.
RD>Можно ли сделать хэш-функцию, которая по числу f из D скажет номер интервала за константное время?
RD>Заранее благодарю!
Если область значений — целые числа и диапазон не слишком велик, то
Создаем массив a[min..max], прописываем a[i] = номер интервала.
Используем теперь f как индекс в этом массиве.
Здравствуйте, RolandD, Вы писали:
RD>Допустим, есть N интервалов разной длины, полностью закрывающую некую допустимую область значений D.
RD>Можно ли сделать хэш-функцию, которая по числу f из D скажет номер интервала за константное время?
RD>Заранее благодарю!
если нужен именно хеш, то можно смотреть в сторону фильтра Блума, но он не дает 100% точного ответа, да и в вашем случае вовсе неэффективен
тут проще было бы сделать дерево интервалов и проверять быстрее чем морочиться с подсчетом хеш функций
Здравствуйте, LelicDsp, Вы писали:
LD>А если интервал удалить надо?
>есть N интервалов разной длины, полностью закрывающую некую допустимую область значений D
LD>>А если интервал удалить надо?
>>есть N интервалов разной длины, полностью закрывающую некую допустимую область значений D
PD>Если удалить — это станет неверным.
Почему? они же могут перекрываться
Здравствуйте, RolandD, Вы писали:
RD>Допустим, есть N интервалов разной длины, полностью закрывающую некую допустимую область значений D. RD>Можно ли сделать хэш-функцию, которая по числу f из D скажет номер интервала за константное время?
Разбиваем D на M равных интервалов. Делаем хэш-таблицу на M слотов. Пусть Dmin, Dmax — нижня и верхняя границы D. Хэш функцией будет
H(f) = [(f - Dmin) / M]
Заносим в таблицу интервалы; понятно что большие попадут в несколько слотов, будет оверхед по памяти. M подбираем, исходя из допустимого количества коллизий. Можно даже анализировать конкретный набор интервалов перед построением, если на это есть время.