data-structures - resolucion - utilizacion de tablas hash
Tablas hash en prólogo (5)
El otro día resolví un acertijo en prólogo y me di cuenta de que si utilizaba otro lenguaje de programación, habría utilizado una tabla / diccionario hash, pero hasta donde sé, esto no es posible en prolog.
Así que mi primera pregunta es: ¿hay algún prólogo que admita una estructura de datos tipo diccionario con las características de rendimiento de una tabla hash?
En segundo lugar, se me ocurrió que, como la mayoría de los prólogos usan una tabla hash para almacenar predicados, podría escribir un predicado contenedor para afirmar y retractar hechos, creando una interfaz de diccionario que aprovecharía la tabla hash subyacente de predicados. Pero, ¿obtendré las características de rendimiento de una tabla hash, o la interfaz agregará gastos generales que reducirían el rendimiento?
Acabo de descubrir que:
La versión 7 de SWI-Prolog introduce dicts como un objeto abstracto con una sintaxis moderna concreta y una notación funcional para acceder a los miembros y también para acceder a las funciones definidas por el usuario.
La sintaxis es la siguiente:
Tag{Key1:Value1, Key2:Value2, ...}
Ver Dicts: estructuras con argumentos con nombre para los detalles.
Tenga en cuenta que :
- Estos son ciudadanos de primera clase del idioma
- La semántica de la unificación entre los dictados puede cambiar en el futuro
- El operador ./2, anteriormente utilizado para el consingimiento, ha sido reutilizado para acceder a los miembros de dict a través de expresiones como el
point{x:1,y:2}.x - Los dicts se pueden modificar destructivamente, pero esto no se recomienda, ya que no es "lógico", por no mencionar que no es funcional.
- La implementación subyacente actual es "un término compuesto que usa el
dictdel functor. El primer argumento es la etiqueta. Los argumentos restantes crean una matriz de pares clave-valor ordenados"
Prolog se da cuenta de los muchos idiomas con un tipo de datos de "mapa" que han surgido durante los últimos 10 años (por ejemplo, mapas en Clojure ).
Algunos entornos Prolog tienen listas de asociaciones , que se pueden usar para crear y editar un diccionario:
Editar:
Es posible que pueda obtener un mejor rendimiento implementando predicados en idiomas extranjeros , por ejemplo:
Los siguientes comentarios abordan su pregunta en un orden que va más o menos de "más específico" a "más general".
Primero, dirigiendo tu comentario concreto:
Habría usado una tabla / diccionario hash, pero hasta donde sé, esto no es posible en Prolog.
Todas las implementaciones de Prolog serias le permiten modificar destructivamente los términos de Prolog, usando por ejemplo setarg/3 . Usar arg/3 y setarg/3 le da O (1) acceso a cada argumento de un término, que es suficiente para implementar una tabla hash exactamente como en otros lenguajes, asumiendo que su sistema no coloca límites arbitrarios en las arias de los términos.
No es una buena idea hacerlo usted mismo , ya que debe tener en cuenta la copia inesperada y el uso compartido de términos en todos los términos. En cambio, confíe en las bibliotecas para hacerlo.
¿Qué bibliotecas? En segundo lugar lo que otros han escrito: en lugar de hash librerías, usa librerías basadas en árboles como library(assoc) , library(avl) etc. Estas no son tan eficientes como hashes en el caso promedio, pero:
- a menudo son lo suficientemente eficientes
- se escalan de manera muy predecible: las operaciones más importantes siempre están en O (log (n)).
También, como otros han escrito, las modificaciones destructivas son incompatibles con la programación lógica, y las bibliotecas de árbol tienen la gran ventaja de que pueden implementarse en ISO Prolog y de una manera pura con una eficiencia asintóticamente óptima .
Finalmente, las extensiones dict de SWI-Prolog no son conformes con ISO , ni siquiera sintácticamente , y por lo tanto no son portátiles para los sistemas de Prolog conformes. Vea los comments Ulrich Neumerkel sobre cómo se puede agregar un punto infijo de una manera conforme a ISO.
No soy un tipo Prolog (solo un observador externo) pero encontré esto:
http://www.sics.se/sicstus/docs/4.0.7/html/sicstus/lib_002davl.html
cuando busqué "árboles equilibrados de mapa finito de prolog". Dice que es una implementación alternativa de listas de asociaciones.
(Por qué pensé en esto: en Haskell, un lenguaje puramente funcional, en lugar de listas de asociaciones o tablas hash, es común usar árboles para diccionarios (persistentes) o mapas finitos. Las búsquedas también son O (log (N)). Data.Map para algunas referencias sobre la implementación de mapas con árboles balanceados.)