Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Чт мар 28, 2024 12:30

...
Google Search
Forth-FAQ Spy Grafic

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 9 ] 
Автор Сообщение
 Заголовок сообщения: Хеширование в форте
СообщениеДобавлено: Вт окт 07, 2008 13:47 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
Автор: Xan Gregg
Статья впервые опубликована в журнале Forth Dimensions XVII/4
оригинальная статья взята отсюда http://www.forth.org/fd/hash.html
Перевел mOleg

Хеширование в форте.

"Компромисс между временем и пространством это хеширование"

Хеширование обеспечивает быстрый метод поиска больших несортированных объемов данных за счет использования дополнительной памяти. Роберт Седжевик в своей книге "Алгоритмы" кратко описывает хеширование как "прямо указывающие ссылки в таблице за счет арифметических преобразований ключей в адресном списке".

Формулировка станет понятна вам в конце статьи, но сначала давайте рассмотрим простой пример.

Допустим, вы должны написать код для управления базой данных с приблизительно 50000 записей, каждую из которых индексирует 16 битное число. Вставки и удаления записей часты, поэтому не могут быть медленными, и поиск записей
происходит часто, поэтому должен так же быть быстрым. При этом у вас 64кб ОЗУ в дополнение к дисковому пространству, где находятся данные, и вы знаете, что каждая запись имеет уникальный трехбуквенный код, подобно аэропортам в США.

Как форт-программист, вы понимаете, что трехбуквенная строка так же является числом, представляемым в 26ричной системе исчисления, и вы делаете таблицу 26x16x16=17,576 ячеек, где каждая ячейка содержит номер записи. Вставка и удаление просты -- вы только должны обновить таблицу вместе с каждой операцией. Поиск записи по ее ключу предполагает только упаковку трех
символов в 15-битное число, и использование этого числа как индекса в таблице. После чего вы получает номер записи.

Если вы можете так сделать, вы уже понимаете основную идею хеширования. Хеширование требует наличия хеш-функции и хеш-таблицы. Хеш-функция конвертирует ключевое значение, такое как текстовая строка или большое число, в индекс внутри хеш-таблицы. Каждая ячейка в хеш-таблице указывает на запись в базе.

В примере код для преобразования трех букв в 15 битное число является хеш-функцией, и таблица с номерами записей - это хеш таблица. Хеш-функция может выглядеть так:
Код:
: ID>INDEX  ( addr -- n )     \ addr points to three uppercase letters
   COUNT [CHAR] A -           \ addr+1 n1
   SWAP COUNT [CHAR] A -      \ n1 addr+2 n2
   SWAP C@ [CHAR] A -         \ n1 n2 n3
   26 * + 26 * + + ;          \ n

Пока у вас 64кб памяти и скорость поиска столь важна, вы можете умножать на 32, вместо 26, так как вы можете использовать операцию сдвига, вместо умножения, то есть не 26 * , а 5 LSHIFT. Получение эффективной хеш-функции очень важно, поэтому она часто пишется на ассемблере.

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

Хеш-функцией может быть почти все. Далее приводится несколько возможностей для преобразования фамилии в 15 битное число:

1) использовать первые три буквы, пять бит на цифру
2) использовать последние три буквы, пять бит на цифру
3) использовать первые пять букв, три бита на цифру (младшие)
4) перемножить все цифры и найти остаток от деления на 2^15
5) взять пять бит с первой буквы, и по два бита со следующих пяти букв
6) использовать три младших бита из байта длины, и по три бита со следующих четырех букв
7) исользовать сумму всех символов строки, взятую по модулю 2^15
8) складывать все символы строки как: буква(i)*2^i, потом 2^15 AND

Я уверен, вы можете придумать больше. Сложность следует за простотой. Вам нужна быстрая функция дающая качественно случайное распределение ключей. Первый приведенный вариант не очень удачен, потому что много имен, вероятно начинаются с одинаковых символов, в результате распределение получится плохим. Четвертый вариант плох по двум причинам: умножение медленная операция, и распределение не очень удачно, так как многократное умножение часто дает четные числа. Седьмой вариант плох, потому что сумма всех цифр не достигнет 2^15. Восьмой вариант пытается побороть маленький диапазон комбинируюя сдвиг и сложение, и может дать хороший результат при качественной настройке.

Любые другие хеш-функции так же могут быть хороши после подстройки. Например, когда вы берете три бита с символа, как решить какие биты стоит выбрать? Верхние три бита очевидно не подходят, потому что все заглавные буквы начинаются с одинаковой трехбитовой последовательности. Младшие три бита смотрятся подходящими, но тоже не достаточно. H, P, X всегда дают 0; B,J,R и Z дают 1 ; а G, O, W - 7; это не выглядит равнозначной группировкой. (Хотя кто знает? Возможно Greggs, Ouversons, и Wests так же часто встречаются, как Browns, Joneses, Rathers, и Zwickkers.) Единственная возможность быть
уверенным - собрать статистику на типичном наборе данных и посмотреть распределение хеш-значений. К сожалению, часто приходится разрабатывать код лишь с частью набора данных, что требует от вас более развитой интуиции.

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

Другое решение - использование вторичной хеш-функции для получения другого индекса, или добавление номера к полученному индексу для получения нового индекса. В любом случае существует возможность появления колизий, которые требуют нахождения другого хеш-индекса, и так далее. Это решение требует чтобы хеш-список имел как минимум одну ссылку на каждую запись.

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

Таким образом хеширование не так просто, как это показалось в первом примере, тем не менее остается очень удобным если время поиска критично. Классически хеширование используется в символьных списках компиляторов. Программа может иметь тысячи символов, которые компилятор должен просматривать очень часто в поисках имени, во время разбора исходных текстов. Я применял хеширование в MacForth словарях, и я знаю, что некоторые другие форты так же используют хешированные словари.

Первый в конце статьи содержит некий общий хеширующий код. FILL-TABLE неумело резервирует записи на лету в пространстве данных, но базовые слова (INSERT-RECORD DELETE-RECORD FIND-RECORD) дают хорошую начальную базу для любого, пытающегося разобраться с хешированием. Код использует односвязный список для разрешения колизий.

ANALYZE-HASH - полезное слово для получения информации о распределении хеш-ключей в хеш-списке. Оно отображает линии, пронумерованные от нуля до девяти, которые показывают как много используется односвязных списков и какой размер они имеют. В другой линии отображается средняя длина списков (без учета пустых). Это значение необходимо минимизировать. Другой полезный инструмент анализа используемый мной в прошлом - отображать хеш таблицу, показывая длину односвязных списков в хеш-таблице. Иногда это разоблачает неиспользуемые индексы, либо индексы, в которых слишком много записей.

Таблица 1 показывает средние длины списков для различных хеш-функций для 3448 форт слов, и размеры хеш-таблиц на 1024 и 4096 ссылок.
<pre>
Таблица 1.
Средняя длина цепочек для различных хеш-функций.
Hash Function W/1024 W/4096
Low bits of first three chars 5.23 3.44
Low bits of length and first two chars 4.36 2.30
Low bits of last three chars 6.31 4.41
Product of first three chars 6.64 3.91
Sum of char(i) * 2^i 3.56 1.57
</pre>
Все эти хеш функции имеют подходящие результаты. Бинарный поиск на этих же данных будет требовать от нас просматривания log2(3448)=11.8 записей. Последний вариант близок к оптимуму (3448.1024=3.37), и является моим любимым. Он похож на функцию, используемую в PowerMacForth, и имеет преимущество в том, что много символов включаются в результат.

В этой таблице впервые упоминает размер хеш-списка (с момента объявления 64К хеш-списка). Чем больше места используется под хеш-список, тем лучше работает поиск (потому что меньше колизий), но конечно же отнимает больше памяти. Компромисс между временем и пространством в хешировании обсужден.

Код:
anew --hash--

( Generic Hashing Code
  Each record must start with one cell for use by the
  hashing code.  It must be followed by a counted string
  which is the key.  Variable-length data may optionally
  follow. )

: ALLOTERASE  ( n -- )  \ utility word
        HERE SWAP DUP ALLOT ERASE ;

1024 CONSTANT /HASHTABLE
CREATE HASHTABLE
        /HASHTABLE CELLS ALLOT

: INIT-HASHING  ( -- )
        HASHTABLE /HASHTABLE CELLS ERASE ;

: MY-HASH-FUNCTION  ( key-addr -- table-index )
        \ you should override this function
        COUNT 0 SWAP 0 DO                       \ addr cur-index
                SWAP COUNT I LSHIFT ROT +
        LOOP NIP
        /HASHTABLE 1- AND ;             \ assumes power of 2

: KEY>INDEX  ( key-addr -- table-index )
        MY-HASH-FUNCTION
        0 MAX /HASHTABLE 1- MIN ;       \ for safety during development

: INSERT-LINK  ( recAddr tableAddr -- )
        \ insert at top of linked list for this index
        DUP @ ROT DUP >R !              \ recAddr.link <= previous top
        R> SWAP ! ;                             \ top <= recAddr

: INSERT-RECORD  ( recAddr -- )
        DUP CELL+ KEY>INDEX CELLS HASHTABLE + INSERT-LINK ;

: DELETE-LINK  ( recAddr tableAddr -- )
        \ remove link from list
        SWAP >R
        BEGIN
                DUP @ R@ <> SWAP @ 0 <> AND
        WHILE
                @       \ no match, so go to next link
        REPEAT
        DUP @ 0 <> IF
                R> @ SWAP !                     \ prev.link <= rec.link
        ELSE
                R> DROP                 \ do nothing if not found
        THEN ;

: DELETE-RECORD  ( recAddr -- )
        DUP CELL+ KEY>INDEX CELLS HASHTABLE + DELETE-LINK ;

: FIND-LINK  ( addr tableAddr -- recAddr or 0 )
        >R BEGIN
                @ DUP
        WHILE
                DUP 1 CELLS + COUNT
                R@ COUNT COMPARE 0= IF
                        R> EXIT         \ found match, so exit
                THEN
                @                               \ no match, so go to next link
        REPEAT ;

: FIND-RECORD  ( addr -- recAddr or 0 )
        DUP KEY>INDEX CELLS HASHTABLE + FIND-LINK ;

\ ---- analysis words ----

: FILL-TABLE ( -- )
        INIT-HASHING
        S" FILEDATA1" R/O OPEN-FILE IF ABORT THEN
        >R      \ stash the file-id
        BEGIN
                HERE 32 CELL+ ALLOTERASE        \ space for text and link
                DUP CELL+ 1+ 31 R@ READ-LINE
                0= OVER 0 <> AND
        WHILE
                DROP                                    \ recAddr bytesRead
                DUP IF
                        OVER CELL+ C!
                        INSERT-RECORD
                ELSE
                        2DROP
                THEN
        REPEAT 2DROP DROP
        R> CLOSE-FILE DROP ;


10 CONSTANT MAX-DEPTH
CREATE DEPTHS MAX-DEPTH CELLS ALLOT
VARIABLE TOTAL-ENTRIES
VARIABLE TOTAL-LISTS

: COUNT-LINKS  ( tableAddr -- n )
        0 SWAP BEGIN @ DUP WHILE SWAP 1+ SWAP REPEAT DROP ;

: ANALYZE-HASH  ( -- )
        MAX-DEPTH 0 DO I CELLS DEPTHS + OFF LOOP
        TOTAL-ENTRIES OFF
        TOTAL-LISTS OFF
        /HASHTABLE 0 DO
                I CELLS HASHTABLE + COUNT-LINKS
                DUP TOTAL-ENTRIES +!
                DUP 0> IF 1 TOTAL-LISTS +! THEN
                MAX-DEPTH 1- MIN
                1 SWAP CELLS DEPTHS + +!
        LOOP
        MAX-DEPTH 0 DO
                CR I 3 .R 2 SPACES I CELLS DEPTHS + @ 5 .R
        LOOP CR ." AVE = "
        TOTAL-ENTRIES @ 100 TOTAL-LISTS @ */
        S>D <# # # [CHAR] . HOLD #S #> TYPE ;


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вт окт 07, 2008 18:54 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
Цитата:
Хеш-функцией может быть почти все.
:shock:

_________________
понимаю некоторую бестолковость некоторых вопросов


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Вт окт 07, 2008 19:11 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
вопрос писал(а):
Цитата:Хеш-функцией может быть почти все.

формально имеется ввиду, что хеш-функций может быть ну очень много, от простейших @ C@ W@

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт окт 10, 2008 01:29 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
решил немного проиллюстрировать методику работу хешей. Как уже было сказано создается таблица, я ее буду показывать, так:
01
02
03
04
05
06


где числа - это ячейки хеш-таблицы

соответственно у нас еще где-то есть записи (например, слова) и ключи(в форте имена) с которыми связаны эти самые функции.
01 -> DUP 
02 -> DROP
03 -> OVER
04 -> SWAP
05 -> NIP
06 -> PICK

если получится создать такую хеш-функцию, которая так будет вычислять хеш-индекс, что имена будут распределены, как показано выше,
НО! в реальности чаще бывает так:
01 -> DUP DROP
02 ->
03 -> OVER NIP PICK
04 -> SWAP
05 ->
06 ->

то есть эти самые колизии, когда на один индекс приходится несколько имен.
В таком случае можно поступать по-разному, например, можно, если индекс занят, занимать следующий свободный:
из такой картинки
01 -> DUP DROP
02 ->
получаем такую
01 -> DUP >>
02 -> DROP

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

Есть и другие решения, но во встреченных мною форт-системах до сих пор встречался единственный наиболее удачный вариант:
01 -> DUP -> DROP
02 ->
03 -> OVER -> NIP -> PICK
04 -> SWAP
05 ->
06 ->

то есть, если имена совпали, то они связываются в односвязный список, начало которого располагаетсях в Хеш-таблице.
При этом хеш-таблицу можно делать небольшой (ускорение поиска и так есть), особенно, если хеш-функция выбрана удачно.
Например, при словаре в 1024 слова и хеш-таблице в 16 ячеек средняя длина цепочек составит 64 слова, что по-сравнению с линейным поиском в 16 раз быстрее. То есть, хеш функция дает информацию о том, где надо начинать искать слово (на какой цепочке, кстати, такие цепочки называются тредами) а дальше получается линейный поиск. Если слова в словаре нет гарантированно, то время на обыскивание словаря в среднем в 16 раз меньше, чем при линейном поиске.
Понятно, что хеш-таблица занимает место, которое жалко тратить. Понятно, что хеш-функция должна быть быстрой, чтобы не прокушать все время, отведенное на поиск (иначе просто не будет выигрыша), так же понятно, что на разных наборах ключей выгирывать (давать более равномерное распределение) будут различные хеш-функции. Кроме того, для каждого словаря делать свою хеш-таблицу расточительно - в словаре может быть всего пара-тройка слов. В то же время большие словари могут быть на столько большими, что и 16 тред будет мало. Вобщем, как всегда надо искать хитроумный компромисс. Наиболее интересным метод ускорения поиска с помощью хеширования сделан в СМАЛ32 (но об этом в другой раз).


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт окт 10, 2008 08:52 
Не в сети

Зарегистрирован: Вт май 09, 2006 12:31
Сообщения: 3438
Благодарил (а): 5 раз.
Поблагодарили: 16 раз.
можно ещё оптимизировать по размеру слов - для слов с маленьким количеством букв простой исчерпывающий, для слов с большим количеством - похитрее, но это усложняет EVALUATE

_________________
понимаю некоторую бестолковость некоторых вопросов


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт окт 10, 2008 18:27 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
вопрос писал(а):
можно ещё оптимизировать по размеру слов - для слов с маленьким количеством букв простой исчерпывающий, для слов с большим количеством - похитрее, но это усложняет EVALUATE

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

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт окт 10, 2008 19:56 
Не в сети
Administrator
Administrator
Аватара пользователя

Зарегистрирован: Вт май 02, 2006 13:19
Сообщения: 3565
Откуда: St.Petersburg
Благодарил (а): 4 раз.
Поблагодарили: 72 раз.
самый простой хеш - 1 байт - сумма всех символов слова

_________________
С уважением, WingLion
Forth-CPU . RuF09WE
Мой Форт
Отсутствие бана это не заслуга юзера, а недоработка модератора (с)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт окт 10, 2008 20:07 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
WingLion писал(а):
самый простой хеш - 1 байт - сумма всех символов слова

не самый простой и не самый удачный.

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения:
СообщениеДобавлено: Пт окт 10, 2008 20:53 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
кстати в хорошей хеш-функции:
- похожие слова должны оказываться на разных тредах: DUP DOP (то есть отличие даже в одном бите);
- слова одинаковой длины должны оказываться на разных тредах;
- слова содержащие одни и те же символы должны находиться на разных тредах: DUP PUD UDP PDU и т.д.
- функция должна быть быстрой.

я в свое время долго эксперементировал с хеш-функциями, и мне понравился более всего следующий метод:

0 в аккумулятор
в цикле для каждого символа строки включая счетчик длины
аккумулятор XOR со значением следующего символа
циклический сдвиг вправо на три бита
результат xor им для получения хеша нужной разрядности

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Часовой пояс: UTC + 3 часа [ Летнее время ]


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

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 11


Вы не можете начинать темы
Вы можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
phpBB сборка от FladeX // Русская поддержка phpBB