существует-ли по perl модуль, реализующий хеш с условием вида "<=" ?Есть пары ключ=>значение, ключи дискретны (time), но значения определены только для некоторых ключей. При задании произвольного ключа Kx надо найти существующеее значение для максимального ключа, не превышающего заданный.
можно использовать qdbm (http://qdbm.sourceforge.net/), Villa API, но придётся подправить C-й код (добавить свою функцию сравнения) и скомпилировать модуль заново.
а такое решение, не повлияет на остальные вещи, использующие gdbm?
я имею в виду именно QDBM, а не GDBM, то есть на GDBM это никак не повлияет. что же касается QDBM, то при использовании API Villa, конструктор базы принимает в качестве аргумента указатель на функцию сравнения (в С), или одну из предопределённых констант (Perl). то есть мы в С описываем свою новую функцию сравнения, и указатель на неё експортируем в Perl в виде ещё одной константы (переменной). т.о. мы ничего не нарушаем из того, что было до нас, просто добавляем что-то новое, что будет использоваться только по желанию и только для конкретных баз.(
http://qdbm.sourceforge.net/plapidoc/Villa.pm.html
http://qdbm.sourceforge.net/spex.html#villaapi
)
спасибо, а gdbm я действительно тормознул.
хотя, я подумал, это тоже не выход. в функции сравнения проверку на <= реализовать можно, но для поиска max, придётся перебирать всех, кто <=. а если это большое число, то получим полный перебор всего.
применить hash-функции также не удасться (а значит и классичеккие хеши), понятно почему. т.ч. выход один -- имитировать хеши через массивы + сортировка + бинарный поиск (к примеру).
фактически, тебе нужно строить b-tree и потом реализовывать спуск до нужного узла. QDBM его и реализует, но к сожалению, нужной функции нет, т.ч. можно реализовать бинарный поиск по базе на C и експортироавать эту функцию в Perl.
да, в том-то и дело, что не хочется делать полный перебор. так ведь хэш и так строится строится по принципу бинарного дерева? или не бинарного?
нет, классические хеши (если точнее, ассоциативные массивы) строятся с использованием т.н. хеш-функций. идея такая: придумываем какую-нибудь функцию, кот. по нашим предполагаемым ключам будет строить числовые значения (хеши). разным ключам может соотв. один и тот же хеш. главное, чтобы таких ключей было не очень много. + важно, чтобы область значений такой функция была конечной.
напр. любые ключи отображаются в диапазон 0..N.
теперь на С хеш можно пострить таким образом:
заводим массив размером в N+1 елемент
елементы массива - указатели на списки
теперь, если нам нужно вставить (ключ, значение), мы по ключу вычисляем хеш (допустим это будет x).
идём в елемент с номером х, последовательно проходим по списку и смотрим есть ли в списке такой ключ. если нет - вставляем новый елемент в конец списка.поэтому важно, чтобы хеш функция давала хорошее распределение, чтобы кол.-во элементов в каждом списке было как можно меньше, и поиск ключа в списке занимал бы "константное" время.
Посмотри Tie::RangeHash.