форумы  помощь  поиск  регистрация  майллист  ВХОД  слежка

Вариант для распечатки		Пред. тема | След. тема
Форумы Программирование под UNIX (Public)
Изначальное сообщение		[Проследить за развитием треда]

"Хеш с нечеткими условиями для perl"
Сообщение от Solotony on 07-Июл-05, 10:30  (MSK)
существует-ли по perl модуль, реализующий хеш с условием вида "<=" ? Есть пары ключ=>значение, ключи дискретны (time), но значения определены только для некоторых ключей. При задании произвольного ключа Kx надо найти существующеее значение для максимального ключа, не превышающего заданный.
	Правка | Высказать мнение | Ответить | Рекомендовать в FAQ | Cообщить модератору | Наверх

Индекс форумов | Темы | Пред. тема | След. тема

Сообщения по теме

1. "Хеш с нечеткими условиями для perl"
Сообщение от ihor on 07-Июл-05, 12:11  (MSK)
можно использовать qdbm (http://qdbm.sourceforge.net/), Villa API, но придётся подправить C-й код (добавить свою функцию сравнения) и скомпилировать модуль заново.
Удалить	Правка | Высказать мнение | Ответить | Рекомендовать в FAQ | Cообщить модератору | Наверх

	2. "Хеш с нечеткими условиями для perl"
	Сообщение от Solotony on 07-Июл-05, 12:34  (MSK)
	а такое решение, не повлияет на остальные вещи, использующие gdbm?
	Удалить	Правка | Высказать мнение | Ответить | Рекомендовать в FAQ | Cообщить модератору | Наверх

	3. "Хеш с нечеткими условиями для perl"
	Сообщение от ihor on 07-Июл-05, 12:52  (MSK)
	я имею в виду именно QDBM, а не GDBM, то есть на GDBM это никак не повлияет. что же касается QDBM, то при использовании API Villa, конструктор базы принимает в качестве аргумента указатель на функцию сравнения (в С), или одну из предопределённых констант (Perl). то есть мы в С описываем свою новую функцию сравнения, и указатель на неё експортируем в Perl в виде ещё одной константы (переменной). т.о. мы ничего не нарушаем из того, что было до нас, просто добавляем что-то новое, что будет использоваться только по желанию и только для конкретных баз. ( http://qdbm.sourceforge.net/plapidoc/Villa.pm.html http://qdbm.sourceforge.net/spex.html#villaapi )
	Удалить	Правка | Высказать мнение | Ответить | Рекомендовать в FAQ | Cообщить модератору | Наверх

	4. "Хеш с нечеткими условиями для perl"
	Сообщение от Solotony on 07-Июл-05, 13:05  (MSK)
	спасибо, а gdbm я действительно тормознул.
	Удалить	Правка | Высказать мнение | Ответить | Рекомендовать в FAQ | Cообщить модератору | Наверх

	5. "Хеш с нечеткими условиями для perl"
	Сообщение от ihor on 07-Июл-05, 14:31  (MSK)
	хотя, я подумал, это тоже не выход. в функции сравнения проверку на <= реализовать можно, но для поиска max, придётся перебирать всех, кто <=. а если это большое число, то получим полный перебор всего. применить hash-функции также не удасться (а значит и классичеккие хеши), понятно почему. т.ч. выход один -- имитировать хеши через массивы + сортировка + бинарный поиск (к примеру).
	Удалить	Правка | Высказать мнение | Ответить | Рекомендовать в FAQ | Cообщить модератору | Наверх

	6. "Хеш с нечеткими условиями для perl"
	Сообщение от ihor on 07-Июл-05, 14:56  (MSK)
	фактически, тебе нужно строить b-tree и потом реализовывать спуск до нужного  узла. QDBM его и реализует, но к сожалению, нужной функции нет, т.ч. можно реализовать бинарный поиск по базе на C и експортироавать эту функцию в Perl.
	Удалить	Правка | Высказать мнение | Ответить | Рекомендовать в FAQ | Cообщить модератору | Наверх

	7. "Хеш с нечеткими условиями для perl"
	Сообщение от Solotony on 07-Июл-05, 15:07  (MSK)
	да, в том-то и дело, что не хочется делать полный перебор. так ведь хэш и так строится строится по принципу бинарного дерева? или не бинарного?
	Удалить	Правка | Высказать мнение | Ответить | Рекомендовать в FAQ | Cообщить модератору | Наверх

	8. "Хеш с нечеткими условиями для perl"
	Сообщение от ihor on 07-Июл-05, 16:42  (MSK)
	нет, классические хеши (если точнее, ассоциативные массивы) строятся с использованием т.н. хеш-функций. идея такая: придумываем какую-нибудь функцию, кот. по нашим предполагаемым ключам будет строить числовые значения (хеши). разным ключам может соотв. один и тот же хеш. главное, чтобы таких ключей было не очень много. + важно, чтобы область значений такой функция была конечной. напр. любые ключи отображаются в диапазон 0..N. теперь на С хеш можно пострить таким образом: заводим массив размером в N+1 елемент елементы массива - указатели на списки теперь, если нам нужно вставить (ключ, значение), мы по ключу вычисляем хеш (допустим это будет x). идём в елемент с номером х, последовательно проходим по списку и смотрим есть ли в списке такой ключ. если нет - вставляем новый елемент в конец списка. поэтому важно, чтобы хеш функция давала хорошее распределение, чтобы кол.-во элементов в каждом списке было как можно меньше, и поиск ключа в списке занимал бы "константное" время.
	Удалить	Правка | Высказать мнение | Ответить | Рекомендовать в FAQ | Cообщить модератору | Наверх

9. "Хеш с нечеткими условиями для perl"
Сообщение от Аноним on 08-Июл-05, 06:53  (MSK)
Посмотри Tie::RangeHash.
Удалить	Правка | Высказать мнение | Ответить | Рекомендовать в FAQ | Cообщить модератору | Наверх

Архив | Удалить	Индекс форумов | Темы | Пред. тема | След. тема
Оцените тред (1=ужас, 5=супер)? [ 1 | 2 | 3 | 4 | 5 ]

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