Войти
В информатика, особенно в функциональном программировании, хеширование - это метод, используемый для разделения значений, которые структурно равны. Термин «хеширование» происходит от реализаций Lisp, которые пытаются повторно использовать cons ячейки, которые были созданы ранее, избегая штрафа выделения памяти. Хеширование чаще всего реализуется с помощью хеш-таблиц, хранящих слабые ссылки, которые могут быть собраны в мусор, когда хранящиеся в них данные не содержат ссылок из-за стола. Было показано, что хеширование приводит к значительному увеличению производительности - как по пространству, так и по времени - для алгоритмов символического и динамического программирования. Интересным свойством хеширования является то, что две структуры могут быть проверены на равенство за постоянное время, что, в свою очередь, может повысить эффективность алгоритмов разделяй и властвуй, когда наборы данных содержат перекрывающиеся блоки.
Простой, не очень эффективный, но подходящий для демонстрации концептуальной реализации мемоизатора с помощью хеш-таблицы и слабых ссылок в Scheme :
;; слабые хеши ;; (require 'hash-table) (define (make-weak-table. args) (apply make-weak-table args)) (define (weak-table-set! table key data)) (let ((w (hash-table -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) (let ((w (hash-table-ref table key #f))) (if w (vector-ref w 0) # f))) ;; фабрика мемоизаторов: для данной процедуры (без побочных эффектов) ;; вернуть процедуру, которая делает то же самое запоминание некоторых результатов ;; в смысле равных? по всему списку аргументов ;; (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)))))
.
