Версия для печати темы

Автор: a3boot 22.03.2007 21:58

Всё ещё занимаюсь поиском в таблице служебных слов...
---
Пока что я пользуюсь чем-то подобным

trunc(a*(ord(s[1]))+b*(ord(s[length(s)])))-k

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




Прикрепленные файлы
 table.txt ( 204 байт ) Кол-во скачиваний: 331

Автор: Malice 23.03.2007 0:20

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

Автор: a3boot 23.03.2007 2:09

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

Предложеная функция

(o - 65) shl 3 xor p

принимает значения от 6 до 248 следовательно для хранения такой таблицы требуется 243 ячейки ([6..242]).

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

Автор: Malice 23.03.2007 4:54

Небольшой перебор выдал вот такую формулу:
хеш=(o-61) xor (p shl 2)-256; хеш=[0..97]

Автор: a3boot 25.03.2007 19:31

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

Автор: Malice 25.03.2007 22:50

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