前几天我在 prolog 中解决了一个难题，并意识到如果我使用另一种编程语言，我会使用哈希表/字典，但据我所知，这在 prolog 中是不可能的。
所以我的第一个问题是，是否有任何 prolog 支持具有哈希表性能特征的类字典数据结构？
其次，我想到，由于大多数 prolog 使用哈希表来存储谓词，我可以编写一个包装谓词来断言和收回事实，创建一个字典接口，该接口将利用谓词的底层哈希表。但是我会得到哈希表的性能特征，还是接口会增加会降低性能的开销？
问问题
6111 次
5 回答
10
我刚刚发现：
SWI-Prolog 版本 7 引入了dicts作为抽象对象，具有具体的现代语法和功能符号，用于访问成员以及用户定义的访问函数。
语法如下：
Tag{Key1:Value1, Key2:Value2, ...}
有关详细信息，请参阅字典：具有命名参数的结构。
注意 ：
- 这些是语言的一等公民
- dicts之间统一的语义在未来可能会改变
- ./2 运算符，以前用于 cons-ing，已被重新用于通过如下表达式访问 dict 成员
point{x:1,y:2}.x - 字典可以被破坏性地修改，但不推荐这样做，因为它是“非逻辑的”，更不用说非功能性的了。
- 当前的底层实现是“使用函子的复合术语
dict。第一个参数是标签。其余参数创建一个排序键值对数组”
当前（2019 年）实施的操作的时间复杂性在 SWI Prolog 手册中的“5.4.5：关于 dicts 的实施说明”下给出：
字典目前使用仿函数表示为复合术语
dict。第一个参数是标签。剩下的参数创建一个排序的键值对数组。这种表示是紧凑的，并保证了良好的局部性。查找顺序为log( N )，而添加值、删除值和与其他 dicts 合并的顺序为N。主要缺点是在大字典中更改值的成本很高，无论是在内存方面还是在时间方面。未来的版本可能会以单独的结构共享密钥或使用二叉树以实现更便宜的更新。问题之一是表示必须保持规范，或者必须扩展统一以补偿替代表示。
并且
SWI-Prolog dicts 是内置的和 SWI-Prolog 扩展。另一种方法是library(assoc)通过库提供基于 AVL 树的映射（因此可能在其他实现中可用）。
于 2014-11-23T01:07:58.980 回答
3
我不是 Prolog 人（只是一个外部观察者），但我发现了这一点：
http://www.sics.se/sicstus/docs/4.0.7/html/sicstus/lib_002davl.html
当我搜索“prolog 有限映射平衡树”时。它说这是关联列表的另一种实现。
（为什么我想到这个：在纯函数式语言 Haskell 中，通常将树用于（持久）字典或有限映射，而不是关联列表或哈希表。查找也是 O(log(N))。参见Data.Map获取有关使用平衡树实现地图的一些参考。）
于 2009-08-25T05:38:08.643 回答
3
以下评论以大致从“更具体”到“更一般”的顺序解决您的问题。
首先，解决您的具体评论：
我会使用哈希表/字典，但据我所知，这在 Prolog 中是不可能的。
所有严肃的 Prolog 实现都允许您破坏性地修改 Prolog 术语，例如使用setarg/3. 使用arg/3andsetarg/3可以让您 O(1) 访问术语的每个参数，这足以像在其他语言中一样实现哈希表，假设您的系统没有对术语的数量设置任意限制。
自己做这件事不是一个好主意，因为您必须考虑到所有术语的意外复制和共享。相反，依靠图书馆来做到这一点。
哪些图书馆？我赞同其他人所写的：不要使用散列库，而是使用基于树的库library(assoc)，例如library(avl)等。在一般情况下，这些库不如散列有效，但是：
- 他们通常足够高效
- 它们的扩展性非常可预测：最重要的操作总是在 O(log(n)) 中。
此外，正如其他人所写的那样，破坏性修改与逻辑编程不兼容，树库具有巨大的优势，即它们可以在ISO Prolog中以一种渐近最优效率的纯粹方式实现。
最后，SWI-Prolog 的 dict 扩展不符合 ISO 标准，甚至在语法上也不符合，因此不能移植到符合标准的 Prolog 系统！请参阅 Ulrich Neumerkel 的评论，了解如何以符合 ISO 的方式添加中缀点。
于 2016-02-15T08:38:17.273 回答