En ciencias de la computación , particularmente en programación funcional , el uso de hash es una técnica utilizada para compartir valores que son estructuralmente iguales. El término consing de hash se origina en implementaciones de Lisp [1] [2] que intentan reutilizar las celdas de cons que se han construido antes, evitando la penalización de la asignación de memoria . La utilización de hash se implementa más comúnmente con tablas hash que almacenan referencias débiles que pueden recolectarse como basura cuando los datos almacenados en ellas no contienen referencias externas a la tabla. [3][4] Se ha demostrado que la utilización de hash proporciona mejoras dramáticas en el rendimiento, tanto en el espacio como en el tiempo, para los algoritmos de programación simbólicos y dinámicos . [ cita requerida ] Una propiedad interesante del uso de hash es que se puede probar la igualdad de dos estructuras en tiempo constante, lo que a su vez puede mejorar la eficiencia de losalgoritmosde dividir y conquistar cuando los conjuntos de datos contienen bloques superpuestos. [5]
Ejemplo
Simple, no muy eficiente, pero adecuado para la demostración de la implementación del concepto de un memoizer mediante tabla hash y referencias débiles en Scheme :
;; hashes débiles ;; ( requiere 'tabla-hash )( define ( make-débil-table . args ) ( aplica make-hash-table args ))( Definir ( débil-table-set! Tabla de clave de datos ) ( dejar que (( w ( tabla hash-ref tabla clave #f ))) ( si w ( vector-set! W 0 datos ) ( dejar que (( w ( marca -weak-vector 1 ))) ( vector-set! w 0 datos ) ( hash-table-set! Table key w )))))( define ( tecla de tabla de referencia de tabla débil ) ( let (( w ( tecla de tabla de referencia de tabla hash #f ))) ( si w ( vector-ref w 0 ) #f ))) ;; fábrica de memoizer: para un procedimiento dado (sin efectos secundarios) ;; devolver un procedimiento que hace lo mismo memorizando algunos de los resultados ;; en el sentido de igual? en toda la lista de argumentos ;; ( definir ( hacer-débil-memoizer proc ) ( dejar (( cache ( hacer-tabla-débil- igual? ))) ( lambda args ( dejar (( x ( débil-tabla-ref cache args ))) ( if ( bwp- objeto? x ) ( dejó (( r ( aplicar proc args ))) ( débil-table-set! caché args r ) r ) x )))))
Ver también
Referencias
- ^ Deutsch, Laurence Peter (1973). "Un verificador de programa interactivo". Palo Alto: Xerox Palo Alto Research Center Terhnical Report CSL-73-1. Cite journal requiere
|journal=
( ayuda ) - ^ Goto, Eiichi (1974). "Monocopias y algoritmos asociativos en Lisp extendido". Tokio: Informe técnico de la Universidad de Tokio TR 74-03. Cite journal requiere
|journal=
( ayuda ) - ^ Allen, John (1978). Anatomía de Lisp . McGraw Hill . ISBN 0-07-001115-X.
- ^ Fillâtre, Jean-Christophe; Conchon, Sylvain (2006). "Consumo de hash modular de tipo seguro". Taller de ML . ACM .
- ^ Liljenzin, Olle (2013). "Conjuntos y mapas de persistencia confluente". arXiv : 1301.3388 . Código Bibliográfico : 2013arXiv1301.3388L . Cite journal requiere
|journal=
( ayuda )
Otras lecturas
- Ershov, AP (1958). "Sobre programación de operaciones aritméticas". Comunicaciones de la ACM . 1 (8): 3–6. doi : 10.1145 / 368892.368907 .
- Jean Goubault. Implementación de lenguajes funcionales con Fast Equality, Sets y Maps: un ejercicio de conversión de hash. En Journées Francophones des Langages Applicatifs (JFLA'93), páginas 222–238, Annecy, febrero de 1993.