Хеширование
В информатике , особенно в функциональном программировании , хеширование — это метод, используемый для совместного использования значений, которые структурно равны. Когда создается значение, например cons -ячейка, метод проверяет, было ли такое значение создано ранее, и если да, то повторно использует предыдущее значение, избегая нового выделения памяти . Полезным свойством хэш-консинга является то, что две структуры можно проверить на равенство за постоянное время посредством равенства указателей, что, в свою очередь, может повысить эффективность алгоритмов «разделяй и властвуй», когда наборы данных содержат перекрывающиеся блоки. [1] Было показано, что хеширование дает значительное улучшение производительности — как по пространству, так и по времени — для символьного и динамического программирования . алгоритмов [ нужна ссылка ]
Консервирование хеширования чаще всего реализуется с помощью хеш-таблиц, в которых хранятся слабые ссылки , которые могут быть удалены сборщиком мусора , если хранящиеся в них данные не содержат ссылок извне таблицы. [2] [3]
Пример
[ редактировать ]Просто, не очень эффективно, но подходит для демонстрации реализации концепции мемоайзера посредством хеш-таблицы и слабых ссылок в Scheme :
;; слабые хеши ;; ( требуется 'хеш-таблица ) ( определить ( make-weak-table . args ) ( применить make-hash-table args )) ( определить ( weak-table-set! table key data ) ( let (( w ( хеш-таблица -ref таблицы ключ #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 #f ключ ) )) ( if w ( vector-ref w 0 ) # ж ))) ;; memoizer Factory: для данной (без побочных эффектов) процедуры ;; вернуть процедуру, которая делает то же самое, запоминая некоторые результаты ;; в смысле равный? по всему списку аргументов ;; ( define ( make-weak-memoizer proc ) ( let (( кэш ( make-weak-table равны? ))) ( лямбда -аргументы ( let (( x ( слабой таблицы-ref кэша аргументы ))) ( if ( bwp- объект? x ) ( let (( r ( применить процедуры аргументы ))) ( набор слабых таблиц! кэша аргументы 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 .
- Жан Губо. Реализация функциональных языков с быстрым равенством, множествами и отображениями: упражнение по хешированию. В «Днях франкоязычных аппликативных языков» (JFLA'93), страницы 222–238, Анси, февраль 1993 г.
 | Эта по информатике статья незавершена . Вы можете помочь Википедии, расширив ее . |