Tablas hash en prolog
Estaba resolviendo un rompecabezas en prolog el otro día y me di cuenta de que si estuviera usando otro lenguaje de programación, habría hecho uso de una tabla hash/diccionario, pero por lo que sé esto no es realmente posible en prolog.
Así que mi primera pregunta es ¿hay algún prolog que soporte una estructura de datos similar a un diccionario con las características de rendimiento de una tabla hash?
En segundo lugar, se me ocurrió que dado que la mayoría de los prologs usan una tabla hash para almacenar predicados, podría escribir un predicado de envoltura para afirmar y retraer hechos, creando una interfaz de diccionario que aprovecharía la tabla hash subyacente de predicados. Pero, ¿obtendría las características de rendimiento de una tabla hash, o la interfaz agregaría gastos generales que reducirían el rendimiento?
5 answers
Acabo de descubrir que:
SWI-Prolog versión 7 introduce dicts como un objeto abstracto con un sintaxis moderna concreta y notación funcional para acceder a los miembros y así como funciones de acceso definidas por el usuario.
La sintaxis es La siguiente:
Tag{Key1:Value1, Key2:Value2, ...}
Ver Dicts: structures with named arguments para los detalles.
Tenga en cuenta que :
- Estos son ciudadanos de primera clase de la idioma
- La semántica de la unificación entre dictados puede cambiar en el futuro
- El.el operador / 2, anteriormente usado para contras, ha sido reutilizado para acceder a miembros dict a través de expresiones como
point{x:1,y:2}.x - Los dictados pueden ser modificados destructivamente pero esto no se recomienda, ya que son "no lógicos", por no hablar de no funcionales.
-
La implementación subyacente actual es "un término compuesto que usa el funtor
dict. El primer argumento es etiqueta. Los argumentos restantes crean una matriz de pares clave-valor ordenados "
Prolog alcanza así a los muchos idiomas con un tipo de datos "map" que han surgido durante los últimos 10 años (por ejemplo, maps in Clojure).
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-11-23 01:07:58
Algunos entornos Prolog tienen Listas de asociación , que se pueden usar para crear y editar un diccionario:
Editar:
Puede obtener un mejor rendimiento implementando predicados en idiomas extranjeros , por ejemplo:
- SWI-Prolog Java o C++
- GNU Prolog Interfaz C
- SICStus C, C++ y Java/. net .
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-11-22 00:08:31
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é "prolog finite map balanced trees". 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 asociación o tablas hash, es común usar árboles para diccionarios (persistentes) o mapas finitos. Búsquedas también son O (log (N)). Véanse los datos .Map para algunas referencias sobre la implementación de mapas con árboles balanceados.)
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2009-08-25 05:38:08
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-02-14 22:39:23
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, abordando su comentario concreto:
Habría hecho uso de una tabla/diccionario hash, pero por lo que sé esto no es realmente posible en Prolog.
Todas las implementaciones serias de Prolog le permiten modificar destructivamente los términos de Prolog, usando por ejemplo setarg/3. Usando arg/3 y setarg/3 le da O (1) acceso a cada argumento de un término, lo cual es suficiente para implementar una tabla hash exactamente como en otros idiomas, suponiendo que su sistema no coloque límites arbitrarios en los arities de los términos.
No es una buena idea hacer esto usted mismo, ya que tiene que tener en cuenta la copia inesperada y el intercambio de términos en todos los términos. En su lugar, confíe en las bibliotecas para hacerlo.
¿Qué bibliotecas? Secundo lo que otros han escrito: En lugar de bibliotecas hash, use bibliotecas basadas en árboles como library(assoc), library(avl) etc. Estos no son tan eficientes como los hashes en el caso promedio, pero:
- a menudo son lo suficientemente eficientes
- escalan muy predeciblemente: Las operaciones más importantes son siempre 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 árboles tienen la enorme ventaja de que pueden implementarse en ISO Prolog y de una manera pura con asintóticamente eficiencia óptima.
Finalmente, las extensiones dict de SWI-Prolog son no conformes con ISO, ni siquiera sintácticamente, y por lo tanto no son portátiles para los sistemas Prolog conformes! Ver la obra de Ulrich Neumerkel observaciones para saber cómo se puede añadir un punto infijo de forma conforme a la norma ISO.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-02-15 08:38:17