我前几天在解决一个prolog的难题时意识到，如果使用另一种编程语言，我会使用哈希表/字典，但据我所知，在prolog中这似乎并不可行。
因此我的第一个问题是：是否有任何支持像哈希表那样性能的字典式数据结构的prolog呢？
第二个问题是，我意识到由于大多数prolog使用哈希表来存储谓词，我可以编写一个包装谓词的谓词，来断言和撤回事实，从而创建一个利用底层谓词哈希表的字典接口。但是，这个接口会增加开销降低性能吗？
5个回答
10
我刚发现:
SWI-Prolog 7版本引入了dicts，作为一个抽象对象具有现代化的语法和功能符号用于访问成员和用户定义的访问函数。
其语法如下:
Tag{Key1:Value1, Key2:Value2, ...}
详细信息请参阅Dicts: structures with named arguments。
需要注意:
- 它们是该语言的一类一等公民
- 未来字典之间的统一语义可能会发生变化
- 以前用于 cons-ing 的 ./2 运算符已经重新定位，可以通过像
point{x:1,y:2}.x这样的表达式访问字典成员 - 字典可以被破坏性地修改，但这并不被推荐，因为它是“非逻辑”的，更不要说非函数化了。
- 当前的底层实现 是“使用 functor
dict的复合术语。第一个参数是标签。其余参数创建一个排序好的键值对数组。”
目前（2019年）实现的操作时间复杂度在 SWI Prolog 手册的“5.4.5：有关字典的实现说明”中给出:
目前，字典表示为使用函数符号为 compound term。其中第一个参数是标签。剩余参数创建了一个已排序的 key-value 数组。
dict是一个标签，第一个参数是标签名。其余参数创建了一个已排序的key-value对数组表示。这种方式紧凑且保证局部性，查找的时间复杂度为log(N)，添加、删除和与其他字典合并的时间复杂度为N。主要缺点在于修改大型字典中的值既费内存也费时间。未来版本可能会在单独结构中共享键或使用二叉树以实现更便宜的更新。其中一个问题是该表示法必须保持规范或者拓展统一性以弥补替代表示方法。
此外
SWI-Prolog字典是内置的SWI-Prolog扩展。另一个选择是
library(assoc)，通过库提供基于AVL树的映射（因此可以在其他实现中使用）。
- David Tonhofer
3
我刚刚看到最近发生了这件事——被改为被接受的答案。我们只需要等几年它就会被开发出来。 - nedned
你是否知道字典计算的时间复杂度，包括get和set操作？它们是像有序映射一样的O(logn)，还是像好的STL C++哈希表一样的O(1)，或者更糟糕的情况？ - user3967841
1@Jason，我已经按照参考手册中的时间复杂度添加了一些时间。 - David Tonhofer
8
一些Prolog环境有关联列表，可以用于创建和编辑字典：
编辑:
通过在外部语言中实现谓词，例如：
您可能能够获得更好的性能。
- Anders Lindahl
4
啊，很酷，那确实是我想要的。不过值得指出的是，这两种实现的查找复杂度为O(log(N))，所以并不像哈希表那样高效。 - nedned
好的观点。我编辑了我的答案并添加了一些 Prolog 接口到外语的链接。 - Anders Lindahl
2另外也请查看YAP Prolog，它非常高效并且实现了几种数据结构（AVL树、Splay树、红黑树等）：http://www.dcc.fc.up.pt/~vsc/Yap/ - Jay
2@Jay，SWI-Prolog在
library(assoc)中也使用AVL树。 - Sebastian3
以下评论按照从“更具体”到“更一般”的顺序回答您的问题。
首先，回答您的具体评论：
引用： 我本来想使用哈希表/字典，但据我所知，在Prolog中这似乎并不可行。
所有严肃的Prolog实现都允许您破坏性地修改Prolog术语，例如使用setarg/3。使用arg/3和setarg/3可以让您O(1)地访问术语的每个参数，这足以像其他语言一样准确地实现哈希表，假设您的系统不会对术语的元数施加任意限制。
自己这样做不是一个好主意，因为您必须考虑所有术语的意外复制和共享。相反，依靠库来完成它。
哪些库？我赞同其他人写的：不要使用哈希库，而是使用基于树的库，如library(assoc)，library(avl)等。这些在平均情况下不如哈希高效，但是：
首先，回答您的具体评论：
引用： 我本来想使用哈希表/字典，但据我所知，在Prolog中这似乎并不可行。
所有严肃的Prolog实现都允许您破坏性地修改Prolog术语，例如使用setarg/3。使用arg/3和setarg/3可以让您O(1)地访问术语的每个参数，这足以像其他语言一样准确地实现哈希表，假设您的系统不会对术语的元数施加任意限制。
自己这样做不是一个好主意，因为您必须考虑所有术语的意外复制和共享。相反，依靠库来完成它。
哪些库？我赞同其他人写的：不要使用哈希库，而是使用基于树的库，如library(assoc)，library(avl)等。这些在平均情况下不如哈希高效，但是：
- 它们通常足够高效。
- 它们的扩展非常可预测：大多数重要操作始终为O(log(n))。
正如其他人所写的那样，破坏性修改与逻辑编程不兼容，而树库具有巨大的优势，即它们可以用ISO Prolog以纯粹的方式实现，并具有渐进最优的效率。
最后，SWI-Prolog的字典扩展不符合ISO标准，甚至在语法上也不兼容，因此不能移植到符合标准的Prolog系统！请参阅Ulrich Neumerkel的 注释，了解如何以符合ISO标准的方式添加中缀点。
- mat
3
我不是Prolog专家（只是个外行），但我找到了这个链接：http://www.sics.se/sicstus/docs/4.0.7/html/sicstus/lib_002davl.html，当我搜索“prolog finite map balanced trees”时。它说这是关联列表的另一种实现方式。
（为什么我会想到这个：在Haskell中，一个纯函数语言，通常使用树来实现（持久）字典或有限映射，而不是关联列表或哈希表。查找也是O(log(N))。有关使用平衡树实现映射的一些参考，请参见Data.Map。）
（为什么我会想到这个：在Haskell中，一个纯函数语言，通常使用树来实现（持久）字典或有限映射，而不是关联列表或哈希表。查找也是O(log(N))。有关使用平衡树实现映射的一些参考，请参见Data.Map。）
- Jared Updike
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接