IPB
ЛогинПароль:

> Правила раздела!

1. Заголовок или название темы должно быть информативным !
2. Все тексты фрагментов программ должны помещаться в теги [code] ... [/code] или [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ" и используйте ПОИСК !
4. НЕ используйте форум для личного общения!
5. Самое главное - это раздел теоретический, т.е. никаких задач и программ (за исключением небольших фрагментов) - для этого есть отдельный раздел!

> Хэш - функция для строк, ищу
сообщение
Сообщение #1





Группа: Пользователи
Сообщений: 5
Пол: Мужской

Репутация: -  0  +


Всё ещё занимаюсь поиском в таблице служебных слов...
---
Пока что я пользуюсь чем-то подобным
trunc(a*(ord(s[1]))+b*(ord(s[length(s)])))-k

Такая функция не имеет коллизий, занимает не много памяти (134 ячейки на 34 слова), но, как мне кажется работает медленно.
---
Может, кто сталкивался с разработкой хэш - функций для строк и готов поделиться опытом.
Таблица слов известна (см. table.txt)



Прикрепленные файлы
Прикрепленный файл  table.txt ( 204 байт ) Кол-во скачиваний: 219
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов(1 - 5)
сообщение
Сообщение #2


Профи
****

Группа: Пользователи
Сообщений: 705
Пол: Мужской

Репутация: -  20  +


Цитата(a3boot @ 22.03.2007 17:58) *

занимает не много памяти (134 ячейки на 34 слова)

Не понял, как такое могло получится.. Если у тебя комбинация 2-х символов уникальна, то для хеша одной строки надо 2 байта максимум.
Пусть: o=ord(s[1]); p=ord(s[length(s)]);
Хеш=o shl 8+p; (от умножений лучше избавиться, т.к медленнно это).
В твоем случае можно и в 1 байт засунуть, просто подогнать, вот так например:
Хеш=(o-65) shl 3 xor p;
Тоже уникально получится..
Если строки любые, то такие методы не пройдут, нужно каждый символ в строке учитывать.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3





Группа: Пользователи
Сообщений: 5
Пол: Мужской

Репутация: -  0  +


Я, наверно, не корректно высказался по поводу ячеек.
---
Под ячейкой в данном случае понимается один элемент массива служебных слов.
---
Наверно, лучше говорить о множестве значений хэш-функции.

Предложеная функция
(o - 65) shl 3 xor p
принимает значения от 6 до 248 следовательно для хранения такой таблицы требуется 243 ячейки ([6..242]).

Моя функция давала значения от 0 до 133 - 134 ячейки, но она проигрывает по времени выше указанной.
---
Время для меня в данный момент является более важной характеристикой, поэтому Огромное спасибо Malice!!!
Может быть предложишь ещё какие - нибудь хэши, а я поэкспериментирую...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Профи
****

Группа: Пользователи
Сообщений: 705
Пол: Мужской

Репутация: -  20  +


Цитата(a3boot @ 22.03.2007 22:09) *

Время для меня в данный момент является более важной характеристикой, поэтому Огромное спасибо Malice!!!
Может быть предложишь ещё какие - нибудь хэши, а я поэкспериментирую...

Небольшой перебор выдал вот такую формулу:
хеш=(o-61) xor (p shl 2)-256; хеш=[0..97]
smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5





Группа: Пользователи
Сообщений: 5
Пол: Мужской

Репутация: -  0  +


Malice, спасибо за помощь.
---
У меня ещё вопрос : нельзя ли сделать более простую функцию, не использующую код последней буквы?
---
Дело в том, что как бы мы не изворачивались, всё равно при обращении к трём элементам массива (нулевому, первому и последнему), и взятию от них ord тратится некое постоянное время, быстрее которого хэш - функцию не вычислить!
---
Видимо придётся оперировать только кодом первого и второго символа(минимальная длина слова - 2), или например кодом первого(второго) символа и длинной...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Профи
****

Группа: Пользователи
Сообщений: 705
Пол: Мужской

Репутация: -  20  +


Только 1-го и 2-го нельзя, т.к. они повторяются в твоем словаре (Else, ElseIF) и хеши одинаковые будут, длина+1+2-ой тоже (RECORD,REPEAT,RETURN).
А так, можно все, экспериментируй и сравнивай результаты.. Могу сказать только, что ни на Length ни на Ord время не тратится. Попробуй переложить на Asm, может сделаешь оптимальнее компилятора паскаля, не вызывай этот код (подсчет хеша) как функцию (на вызов тратится время тоже).
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.10.2020 20:33
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name