Хеширование
В информатике , особенно в функциональном программировании , хеширование — это метод, используемый для совместного использования значений, которые структурно равны. Когда создается значение, например cons -ячейка, метод проверяет, было ли такое значение создано ранее, и если да, то повторно использует предыдущее значение, избегая нового выделения памяти . Полезным свойством хэш-консинга является то, что две структуры можно проверить на равенство за постоянное время посредством равенства указателей, что, в свою очередь, может повысить эффективность алгоритмов «разделяй и властвуй», когда наборы данных содержат перекрывающиеся блоки. [1] Было показано, что хеширование дает значительное улучшение производительности — как пространства, так и времени — для символьного и динамического программирования . алгоритмов [ нужна ссылка ]
Консервирование хеширования чаще всего реализуется с помощью хеш-таблиц, в которых хранятся слабые ссылки , которые могут быть удалены сборщиком мусора , если хранящиеся в них данные не содержат ссылок извне таблицы. [2] [3]
Пример
[ редактировать ]Просто, не очень эффективно, но подходит для демонстрации реализации концепции мемоайзера посредством хеш-таблицы и слабых ссылок в Scheme :
;; weak hashes
;;
(require 'hash-table)
(define (make-weak-table . args)
(apply make-hash-table args))
(define (weak-table-set! table key data)
(let ((w (hash-table-ref table key #f)))
(if w
(vector-set! w 0 data)
(let ((w (make-weak-vector 1)))
(vector-set! w 0 data)
(hash-table-set! table key w)))))
(define (weak-table-ref table key)
(let ((w (hash-table-ref table key #f)))
(if w
(vector-ref w 0)
#f)))
;; memoizer factory: for given (side-effect-free) procedure,
;; return a procedure which does the same memoizing some of results
;; in the sense of equal? on the whole list of args
;;
(define (make-weak-memoizer proc)
(let ((cache (make-weak-table equal?)))
(lambda args
(let ((x (weak-table-ref cache args)))
(if (bwp-object? x)
(let ((r (apply proc args)))
(weak-table-set! cache args r)
r)
x)))))
История
[ редактировать ]Методика компиляции хэш-консенса была предложена А. П. Ершовым в 1958 году. [4] [5] Термин «хэш-консинг» возник из реализаций Lisp в 1970-х годах. [6] [7]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Лильензин, Олле (2013). «Слитно устойчивые множества и карты». arXiv : 1301.3388 [ cs.DS ].
- ^ Аллен, Джон (1978). Анатомия Лиспа . МакГроу Хилл . ISBN 0-07-001115-Х .
- ^ Филлиатр, Жан-Кристоф; Коншон, Сильвен (2006). «Типобезопасное модульное хэширование». Семинар по ML . АКМ .
- ^ Ершов А.П. (1 августа 1958 г.). «О программировании арифметических операций» . Коммуникации АКМ . 1 (8): 3–6. дои : 10.1145/368892.368907 . ISSN 0001-0782 . S2CID 15986378 .
- ^ «Совместное использование и устранение общих подвыражений в компиляции EDSL» . okmij.org . Проверено 27 апреля 2023 г.
- ^ Дойч, Лоуренс Питер (1973). Интерактивный верификатор программы (PDF) (доктор философии). Пало-Альто: исследовательского центра Xerox Пало-Альто CSL-73-1. Технический отчет
- ^ Гото, Эйичи (1974). Монокопия и ассоциативные алгоритмы в расширенном Lisp (PDF) (Технический отчет). Токио: Технический отчет Токийского университета TR 74-03.
Дальнейшее чтение
[ редактировать ]- Ершов, А.П. (1958). «О программировании арифметических операций» . Коммуникации АКМ . 1 (8): 3–6. дои : 10.1145/368892.368907 . S2CID 15986378 .
- Жан Губо. Реализация функциональных языков с быстрым равенством, множествами и отображениями: упражнение в хеш-консенсировании. В Journées Francophones des Langages Applicatifs (JFLA'93), страницы 222–238, Анси, февраль 1993 г.
 | Эта по информатике статья незавершена . Вы можете помочь Википедии, расширив ее . |