Метод ускорения поиска слов в словаре с коррекцией коллизий

chess

Алгоритм:
Определяется для всех слов словаря максимальное значение хэша.
Заводится таблица, размер которой в 4 раза больше этого значения.
Эта таблица обнуляется и в нее записываются адреса полей имен всех слов словаря
по смещению, равном их хэшам умноженным на 4.

Алгоритм вычисления хэшей допускает коллизии - совпадения хэшей.
Если после проверки на совпадение имени слова, которое ищем, с именем в словарной статье,
полученным из хэш-таблицы, имена несовпали, то осуществляется переход к стандартной процедуре поиска,
а если совпали, то сразу вычисляется адрес поля кода для слова.

Реализация:

Код:

0 VALUE MAX-HASH

: GET-HASH ( addr u -- hash)
0 -ROT OVER + SWAP DO I C@ BL - DUP DUP 2/ XOR + + LOOP ;

: FIND-MAX-HASH ( -- )
0 TO MAX-HASH CONTEXT @ @ >R
BEGIN R@ WHILE R@ COUNT GET-HASH MAX-HASH MAX TO MAX-HASH
      R> CDR >R
REPEAT RDROP ;

FIND-MAX-HASH
CREATE T-HASH MAX-HASH CELLS DUP ALLOT T-HASH SWAP ERASE

: T-HASH! ( -- )
CONTEXT @ @ >R
BEGIN R@ WHILE R@ COUNT OVER SWAP
      GET-HASH DUP MAX-HASH <
      IF CELLS T-HASH + ! ELSE 2DROP THEN
      R> CDR >R
REPEAT RDROP ;  T-HASH!

: SFIND-H ( addr u -- addr u 0 | xt 1 | xt -1 )
2DUP 2DUP 2>R GET-HASH DUP MAX-HASH <
IF CELLS T-HASH + @ DUP 0<>
   IF DUP >R 1- COUNT COMPARE 0=
      IF R@ 6 - @ R> 2- C@ &IMMEDIATE AND
         IF 1 ELSE TRUE THEN
         RDROP RDROP
      ELSE RDROP 2R> SFIND THEN
   ELSE DROP 2DROP 2R> SFIND THEN
ELSE DROP 2DROP 2R> SFIND THEN
;

\ EOF тесты

: WRD1 \ стандартный поиск слов словаря
T-HASH MAX-HASH CELLS + T-HASH
DO I @ DUP 0<> IF 1- COUNT SFIND   2DROP ELSE DROP THEN CELL +LOOP ;

: WRD2 \ поиск слов словаря по их хэшам
T-HASH MAX-HASH CELLS + T-HASH
DO I @ DUP 0<> IF 1- COUNT SFIND-H 2DROP ELSE DROP THEN CELL +LOOP ;

: S1 10000 0 DO WRD1 LOOP ." 1 " ;
: S2 10000 0 DO WRD2 LOOP ." 2 " ;



MAX-HASH . CR
S1 S2

Итог: ускорение поиска в 20 раз
Ps. В хэш таблицу попало 892 слова(они и искались) при общем количестве слов в словаре FORTH - 921 слово.
В реальности часто используется только малая часть словаря, поэтому ускорение будет больше чем 20.
Сколько неправильных адресов имени в хэш-таблице не смотрел, но они там наверняка есть, и обходилось это
переходом к стандартной процедуре поиска.

mOleg

я когда-то исследовал простые алгоритмы хешей для имен слов.
Наиболее удачным, на сколько помню (то есть равномерным) был следующий:
XOR значения символа со значением накопителя и циклический сдвиг вправо на три бита в конце XOR 4 байт между собой для получения однобайтного значения, чего вполне достаточно для любого словаря.

да, я не понял причем "коррекция колизий" в названии топика

rvm

[quote="chess"]Итог: ускорение поиска в 20 раз[/quote]
1. А на сколько быстрей транслируется проект килобайт на 100? (например, spf-asm и disasm)
2. Чтобы не с нуля начинать, см. файлы *hash* и quick-swl3.f в devel

chess

mOleg писал(а):

да, я не понял причем "коррекция колизий" в названии топика

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

chess

rvm писал(а):

1. А на сколько быстрей транслируется проект килобайт на 100? (например, spf-asm и disasm)

Для этого надо пересобрать СПФ с измененным алгоритмом поиска. Будет время - сделаю.
(что-то не вижу простого варианта подключить новый поиск внешней библиотекой).
Мне только не понятно, что принципиально нового даст такое сравнение.

rvm писал(а):

2. Чтобы не с нуля начинать, см. файлы *hash* и quick-swl3.f в devel

Я начинал когда-то смотреть, то что вы предложили, но наткнулся на цифру 43% ускорения и стало неинтересно.
Может что не понял. Посмотрю еще раз.

mOleg

chess писал(а):

mOleg писал(а):да, я не понял причем "коррекция колизий" в названии топика
При том, что нет гарантии несовпадения хэшей для слов в словаре.

мнда, боюсь вам стоит посмотреть, как был реализован поиск внутри, например smal32, или старого Info-Forth.
Обычно хеш таблица делается небольшая (на 16-256-1024 элемента) и все слова, у которых хеш совпадает добавляются в линейный список.
То есть ускорение идет в разы и так, и память под хеш не много места занимает.
С другой стороны в форте могут быть одинаковые имена

rvm

chess писал(а):

(что-то не вижу простого варианта подключить новый поиск внешней библиотекой).
Мне только не понятно, что принципиально нового даст такое сравнение.

По иронии, ответы на непонятки лежат как раз там, где "стало неинтересно" ;)

chess

mOleg писал(а):

мнда, боюсь вам стоит посмотреть, как был реализован поиск внутри, например smal32, или старого Info-Forth.
Обычно хеш таблица делается небольшая (на 16-256-1024 элемента) и все слова, у которых хеш совпадает добавляются в линейный список.
То есть ускорение идет в разы и так, и память под хеш не много места занимает.
С другой стороны в форте могут быть одинаковые имена Cool

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

Код:

: WRITE-HASH ( --)  LATEST DUP COUNT GET-HASH CELLS T-HASH + ! ;
: : ( --) HEADER WRITE-HASH ] HIDE ;

Для остальных слов, создающих новые слова, нужно поступить аналогично.
В линейный список словаря все заносится как и обычно.
Говорить о совпадении имен слов можно только при наличии нескольких словарей. Но для каждого словаря
можно завести свою хэш-таблицу. Вопрос о минимизации памяти под хэш-таблицы считаю риторическим - памяти как раз много и будет еще больше(особенно на PC). Что же касается совпадения имен слов, вот тут пока непонятно как реализовать концепцию NOTFOUND - в существующем виде она не подпадает под хэширование.

mOleg

chess писал(а):

Вот как раз такой подход к ускорению поиска мне не подходит, так как чтобы зафиксировать факт совпадения хэшей у разных имен слов, нужно все слова перебрать

не верно. Ты меня не понял.
В момент создания слова рассчитывается его(слова) хеш, при этом функция хеша выбирается легкая и количество хешей ограничено, например одним байтом (256), после того, как хеш функция вычислена слово добавляется в линейный список, который начинается в хеш таблице, то есть получается этакая палочка, на которую навешаны нитки с бусинами слов

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

вопрос

поделенный поиск, причём делитель равен числу хеш-значений

mOleg

кстати, когда-то читал статейку, где автор предлагал делать следующее ускорение поиска.
Список слов остается линейным, но при каждом нахождении слова, оно пересоединяется в начало списка.

chess

mOleg писал(а):

не верно. Ты меня не понял.
В момент создания слова рассчитывается его(слова) хеш, при этом функция хеша выбирается легкая и количество хешей ограничено, например одним байтом (256), после того, как хеш функция вычислена слово добавляется в линейный список, который начинается в хеш таблице, то есть получается этакая палочка, на которую навешаны нитки с бусинами слов Cool Поиск производится по такой схеме значительно быстрее: сначала ищется хеш функция искомого слова, потом из рассчитанной ячейки хеш таблицы выбирается адрес последнего добавленного(на нитку) слова, и дальше линейно на нитке ищется слово. При этом, если функция хеша достаточно равномерна, то поиск ускоряется даже более, чем в 20 раз, и зависит от количества ниток (тред).

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

вопрос

Цитата:

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

Можно совершенствовать систему поиска и ничего удивительного, если она будет лучше... но нужна стратегия - такая компиляция, после которой не нужен поиск ...

mOleg

chess писал(а):

Да-не понял, потому, что описание алгоритма неточное, допускающее множественное толкование и как следствие много вопросов.

я ведь не справочное руководство

просто более подробно объяснять долго. А источники, где можно подсмотреть классическое решение названы.
Кстати линейный список, как в СПФ - это нововведение от избытка производительности. Раньше себе форты такие глупости не позволяли. К тому же СПФ особенная система.

chess писал(а):

Скорость трансляции зависит от множества факторов и не факт, что схема поиска слов, принятая в SMALL32 будет эффективнее в СПФ, чем предложенная мной.

подозреваю, что будет быстрее

Mihail

mOleg писал(а):

К тому же СПФ особенная система.

Чем она особенная?

Метод ускорения поиска слов в словаре с коррекцией коллизий

Кто сейчас на конференции