IisNuINu 4 часа назад

GIMP Script-Fu Первый Дан. Реализация Хеш-Таблицы

Средний

9 мин

227

Программирование*Lisp*Алгоритмы*

Туториал

Приблизительно такая структура хеш-таблицы у нас и будет.

Библиотека функций к Script-fu

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

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

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

Хеш функция для строк.

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

(define (string-weight-sum2 str)
   (let ((l (string-length str)))
      (do ((i (- l 1) (- i 1))
           (p 1 (+ p 1))
           (rez 0 (+ rez
                     (* p (char->integer (string-ref str i))))))
            ((< i 0) rez)
         )))

пробуем

(string-weight-sum2 "ААВГ")
;;10407
(string-weight-sum2 "АВВА")
;;10410
(string-weight-sum2 "ААВА")
;;10404
(string-weight-sum2 "ААГА")
;;10406
(string-weight-sum2 "ААГБ")
;;10407

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

Организация хеш-таблицы

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

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

Бороться с этими недостатками можно, но данный вопрос выходит за рамки этой статьи.

;;хеш у нас будет пара(pair)! в которой
;;car  - метка структуры данных HASTABLE
;;cadr - текущая заполненность хеш таблицы(нужна для динамического увеличения
;;таблицы
;;cddr - указатель на данные хеш таблицы(вектор)
(define (make-hash init-size)
   (cons 'HASHTABLE (cons 0 (make-vector init-size))))

(define (hash? obj)
   (and (pair? obj) (eq? (car obj)  'HASHTABLE)))

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

Поиск

Для поиска в таблице мы для каждого входящего ключа(и его хеш-кода) создаём функцию сравнения.

;;ячейка в хеш таблице это список совпадающих(колизий) ключей
;;'((key key-int . value) () () ....)
;; каждое вхождение в список совпадений это список из трех элементов
;; ключа, числового представления ключа, и значения в cdr второго эл. списка.
(define (make-func-compare-key key key-int)
   (cond ((integer? key)
          (lambda (k ki)
             (and (integer? k) (= k key))))
         ((string? key)
          (lambda (k ki)
             (and (string? k) (= key-int ki) (string=? key k))))
         ((char? key)
          (lambda (k ki)
             (and (char? k) (= key-int ki) (char=? key k))))
         ((symbol? key)
          (lambda (k ki)
             (and (symbol? k) (eq? key k))))
         (#t
          (lambda (k ki)
             #f))
         ))

(define (key2int key)
   (cond ((integer? key)
          key)
         ((string? key)
          (string-weight-sum2 key))
         ((char? key)
          (char->integer key))
         ((symbol? key)
          (string-weight-sum2 (symbol->string key)))
         (#t
          0)
         ))

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

Функция осуществляющая поиск по ключу в хеш-таблице:

(define (hash-ref hash key)
   (let* ((rez (cons #f nil))
          (tbl (cddr hash))
          (key-int (key2int key))
          (compare-key (make-func-compare-key key key-int))
          (colizions (vector-ref tbl
                                 (modulo key-int
                                         (vector-length tbl)))))
      (do ((cur colizions (cdr cur)))
            ((or (null? cur) (car rez)))
         (if (compare-key (caar cur) (cadar cur))
             (begin
                (set-car! rez #t)
                (set-cdr! rez (cddar cur)))))
      rez))

Добавление в хеш-таблицу.

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

;; определяет необходимость расширения хеш-таблицы
(define (need-expand-hash-table? hash)
   (> (/ (* 1.0 (cadr hash)) (vector-length (cddr hash)))
      0.75)) ;;фактор "заполненности", можно увеличить или уменьшить.

;;функция расширения хеш-таблицы
(define (expand-hash-table! hash)
   (let* ((prev (cddr hash))
          (prev-len (vector-length prev))
          (new-len  (* 2 prev-len))
          (tbl (make-vector new-len))
          (new-cap  0))
      (set-cdr! (cdr hash) tbl)
      (do ((i 0 (+ i 1)))
            ((>= i prev-len)
             (set-car! (cdr hash) new-cap)
             hash)
         (let ((coliz (vector-ref prev i)))
            (do ((cur coliz (cdr cur)))
                  ((null? cur))
               (let ((key     (caar  cur))
                     (key-int (cadar cur))
                     (val     (cddar cur)))
                  (if (hashtbl-set! tbl key key-int val)
                      (set! new-cap (+ new-cap 1))))))
         )))

;;само добавление в хеш-таблицу.
(define (hashtbl-set! tbl key key-int val)
   (let* ((compare-key (make-func-compare-key key key-int))
          (ind (modulo key-int (vector-length tbl)))
          (colizions (vector-ref tbl ind))
          (new-key #t))
      (do ((cur colizions (cdr cur)))
            ((or (null? cur) (not new-key)))
         (if (compare-key (caar cur) (cadar cur))
             (begin
                (set-cdr! (cdar cur) val)
                (set! new-key #f))))
      (if new-key
          (vector-set! tbl ind
                       (cons (cons key
                                   (cons key-int val))
                             colizions) ))
      new-key))

;;внешний интерфейс добавления нового элемента в хеш таблицу
(define (hash-set! hash key val)
   (if (need-expand-hash-table? hash)
       (expand-hash-table! hash))
   (let ((tbl (cddr hash))
         (key-int (key2int key)))
      (if (hashtbl-set! tbl key key-int val)
          ;;если добавили увелич. содерж.элем., если изм. то ничего не делаем
          (set-car! (cdr hash) (+ 1 (cadr hash)))))
   hash)

Удаление элемента по ключу:

;; удаляет элемент с заданным ключём из хеш таблицы
(define (hash-del! hash key)
   (let* ((tbl (cddr hash))
          (key-int (key2int key))
          (compare-key (make-func-compare-key key key-int))
          (ind (modulo key-int (vector-length tbl))) ;;вот он "мгновенный доступ" по ключу.
          (colizions (vector-ref tbl ind))           ;;вся оставшаяся проблема это обработать коллизии
          (new-col '())
          (need-change #f))
      (do ((cur colizions (cdr cur)))
            ((null? cur)
             (if need-change
                 (vector-set! tbl ind new-col)))
         (if (compare-key (caar cur) (cadar cur))
             (begin
                (if (> (cadr hash) 0) ;;нашли! правим счётчик 
                    (set-car! (cdr hash) (- (cadr hash) 1)))
                (set! need-change #t)) 
             (begin ;; все остальные элементы в новый список
                (set! new-col
                   (cons (car cur) new-col)))))
      need-change))

Мелочи

Остальные функции, это уже обслуживающие функции, служащие для удобста работы с хеш-таблицей

;;возвращает список имеющихся ключей хеш таблицы
(define (hash-keys hash)
   (let* ((rez '())
          (tbl (cddr hash))
          (up-idx (vector-length tbl)))
      (do ((i 0 (+ i 1)))
            ((>= i up-idx) rez)
         (let ((colizions (vector-ref tbl i)))
            (do ((cur colizions (cdr cur)))
                  ((null? cur))
               (set! rez (cons (caar cur)
                               rez)))
            ))))


;;возвращает список имеющихся пар в хеш таблице
(define (hash2pairs hash)
   (let* ((rez '())
          (tbl (cddr hash))
          (up-idx (vector-length tbl)))
      (do ((i 0 (+ i 1)))
            ((>= i up-idx) rez)
         (let ((colizions (vector-ref tbl i)))
            (do ((cur colizions (cdr cur)))
                  ((null? cur))
               (set! rez (cons
                          (cons (caar cur) (cadar cur))
                               rez)))
            ))))

;;функция создания хеш-таблицы по списку пар.
(define (pairs2hash lst)
   (let* ((len-hash (* 2 (length lst)))
          (h (make-hash len-hash)))
      (do ((cur lst (cdr cur)))
            ((null? cur) h)
         (hash-set! h (caar cur) (cdar cur)))))

Тесты

подготовка:

;;загрузка функций хеш-таблицы в скрипт-фу.
(define path-home (getenv "HOME"))
(define path-lib (string-append path-home "/work/gimp/lib/"))
(define path-work (string-append path-home "/work/gimp/"))
(load (string-append path-lib "util.scm"))
(load (string-append path-lib "hashtable.scm")) ;;

;;создание хеш-таблици из списка пар - ключ, значение.
(define h1
   (pairs2hash
    `((T1 . 1) (T2 . 2) (T3 . 3) (T4 . 4) (T5 . 5)
      (T11 . 11) (T12 . 12) (T13 . 13) (T14 . 14) (T15 . 15)
      (T111 . 111) (T112 . 112) (T113 . 113) (T114 . 114) (T115 . 115)
      )))
(prn h1)
;;(HASHTABLE 15 . #(((T111 630 . 111)) ((T112 631 . 112)) ((T113 632 . 113)) ((T114 633 . 114))
;; ((T115 634 . 115)) () () ((T1 217 . 1)) ((T2 218 . 2)) ((T11 399 . 11) (T3 219 . 3))
;; ((T12 400 . 12) (T4 220 . 4)) ((T13 401 . 13) (T5 221 . 5)) ((T14 402 . 14)) ((T15 403 . 15))
;; () () () () () () () () () () () () () () () ()))#t
;; найти значение по ключу
(hash-ref h1 't113)
;;(#f)
(hash-ref h1 'T113)
;;(#t . 113)
;;установить значение для ключа
(hash-set! h1 'T113 21)
;;21
(hash-ref h1 'T113)
;;(#t . 21)
 (hash-del! h1 'T113)
;;#t
(hash-ref h1 'T113)
;;(#f)
(prn h1)
;;ищем где 'T113, если его нет - то всё хорошо.

Ключи-списки, Ключи-массивы.

Как же мы можем добавить в хеш-таблицу возможность работать с составными ключами, т.е использовать в качестве ключей массивы и списки? Ну во-первых необхдимо описать некие функции, которые будут создавать хеш-ключ, для этих структур. Самый простой способ это уже описанный нами алгоритм присвоения веса каждой позиции составной структуры. Во вторых надо изменить указанные выше функции make-func-compare-key - так что бы она создавала функцию сравнения для списков и массивов. И функцию key2int, чтобы она могла по представленному ей значеню массива или списка, выдать некое числовое значение - хеш-значение ключа, и работать она будет основываясь на наших функциях подсчитывающих сумму взвешенных элементов.

(define (pair-weight-sum lst)
   (do ((cur lst (cdr cur))
        (p 1 (+ p 1))
        (rez 0 (+ rez
                  (* p (key2int (car cur))))))
        ((null? cur) rez)
	))

(define (vector-weight-sum arr)
   (let ((l (vector-length arr)))
      (do ((i 0 (+ i 1))
           (p 1 (+ p 1))
           (rez 0 (+ rez
                     (* p (key2int (vector-ref arr i))))))
            ((>= i l) rez)
	)))

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

(define (make-func-compare-key key key-int)
   (cond ((integer? key)
          (lambda (k ki)
             (and (integer? k) (= k key))))
         ((string? key)
          (lambda (k ki)
             (and (string? k) (= key-int ki) (string=? key k))))
         ((char? key)
          (lambda (k ki)
             (and (char? k) (= key-int ki) (char=? key k))))
         ((symbol? key)
          (lambda (k ki)
             (and (symbol? k) (eq? key k))))
         ((pair? key)
          (lambda (k ki)
             (and (= key-int ki) (equal? key k))))
         ((vector? key)
          (lambda (k ki)
             (and (= key-int ki) (equal? key k))))
         (#t
          (lambda (k ki)
             #f))
         ))

(define (key2int key)
   (abs 
     (cond ((integer? key)
           key)
          ((string? key)
           (string-weight-sum2 key))
          ((char? key)
           (char->integer key))
          ((symbol? key)
           (string-weight-sum2 (symbol->string key)))
          ((pair? key)
           (pair-weight-sum key))
          ((vector? key)
           (vector-weight-sum key))
          (#t
           0)
         )))

Как видите изменения минимальные. Однако есть особенность функция key2int зависит от функций pair-weight-sum и vector-weight-sum, которые в свою очередь сами зависят от key2int. Это взаимно-рекурсивные функции. Таким образом мы сможем обрабатывать очень сложные ключи, например списки содержащие массивы, элементами которых могут быть списки или массивы. Правда вычисление ключа для таких структур будет гораздо дольше, чем у простых ключей, но в некоторых случаях такая возможность поможет ускорить решение очень сложной проблемы.

Эти функции сведены в файл hashtable2.scm с определениями раскрывающими макросы в функциях. Протестируем их.

Сначала ключи массивы:

(load (string-append path-lib "hashtable2.scm"))
;; тестируем возможность создания хеш-кода ключей для массивов
(key2int #(1 2 3)) ;;14
(key2int #(1 2 2)) ;;11
(key2int #(2 3 1)) ;;11 - ая яй!!! "провал хеш-функции" но к счасть это не смертельно
;; создаем хеш-таблицу из пар.
(define h1 (pairs2hash 
            `((#(1 2 3) . 51)
   			  (#(1 2 2) . 52)
	   		  (#(2 3 1) . 53))))
;; получение значений по ключу, ключ это массив
(hash-ref h1 #(1 2 3)) ;;(#t . 51)
(hash-ref h1 #(1 2 2)) ;;(#t . 52)
(hash-ref h1 #(2 3 1)) ;;(#t . 53)
;; установка значений
(hash-set! h1 #(4 2 1) 71) ;;71 
;; проверка
(hash-ref h1 #(4 2 1)) ;;(#t . 71)

Тестируем ключи списки.

;; тест возможности создания хеш-кода для списков
(key2int '(a b c)) ;;590
;; создаем хеш-таблицу из пар
(define h2 (pairs2hash 
            `(((a b c) . 51)
			     ((b c d) . 52)
			     ((x y z) . 53))))
;; получаем значения по ключу, где ключ это список 
(hash-ref h2 '(b c d))  ;;(#t . 52)
;; пример списка имеющего хеш-код, одинаковый с другим ключём-списком.
(key2int '(c d a)) ;;590
;; попробуем найти значение, но такого ключа на самом деле нет!
(hash-ref h2 '(c d a))   ;;(#f)
;;установка значения о ключу
(hash-set! h2 '(c d a) 1)
;;посмотрим на сам хеш массив
;;(HASHTABLE 4 . #(() () 
;;                 (((c d a) 590 . 1) ((x y z) 728 . 53) ((b c d) 596 . 52) 
;;                  ((a b c) 590 . 51)) () () ()))
;; все значения попали в один список коллизий! это плохо, но не страшно
;; такое возможно при малых размерах хеш-массива.

;;добавим новые значения в хеш таблицу
(hash-set! h2 '(c d a) 2)
(hash-set! h2 '(a c d a) 1)
(hash-set! h2 '(b c d a) 11) ;;11

;;таблица расширилась, посмотрим на неё снова.
h2
;;(HASHTABLE 6 . #((((b c d a) 984 . 11)) () 
;;                 (((a b c) 590 . 51) ((c d a) 590 . 2)) () () () () () 
;;                 (((b c d) 596 . 52) ((x y z) 728 . 53)) () () 
;;				   (((a c d a) 983 . 1))))
;; теперь значительное количество коллизий распределились по массиву.

Заключение

В последствии я добавил возможность использовать в качестве ключей объекты, но об этом ещё рано рассказывать, т.к. про систему объектов, а вернее о том как реализовать ООП на схеме, я ещё ничего не говорил. А там есть о чём рассказать(в принципе исходники то я выложил). Я реализовал целых 3 объектных системы:

Это стандартная объектная система схемы основанная на окружениях и функциях-замыканиях.
Это аналог GOOP(Guile OOP), там массово используется эта реализация хеш-таблицы, и отличает ее от лисповской системы ООП, то что за каждый вызов обобщённой функции вызывается только один, соответствующий объекту метод.
Это аналог CLOS(Common Lisp Object System), но без реализации MOP. На мой взгляд MOP он нужен только для экспериментов с объектной системой. Отличается от второго варианта тем, что вызываемой обобщённой функции может соответствовать вызов целой комбинации методов(primary after before around). Думаю с этой концепцией ООП вообще мало кто знаком.

Так что как говориться "следите за выпусками", возможно когда то и до описания реализации ООП дойду.

Теги:

Хабы: