我前几天在解决一个prolog的难题时意识到,如果使用另一种编程语言,我会使用哈希表/字典,但据我所知,在prolog中这似乎并不可行。
因此我的第一个问题是:是否有任何支持像哈希表那样性能的字典式数据结构的prolog呢?
第二个问题是,我意识到由于大多数prolog使用哈希表来存储谓词,我可以编写一个包装谓词的谓词,来断言和撤回事实,从而创建一个利用底层谓词哈希表的字典接口。但是,这个接口会增加开销降低性能吗?
我前几天在解决一个prolog的难题时意识到,如果使用另一种编程语言,我会使用哈希表/字典,但据我所知,在prolog中这似乎并不可行。
因此我的第一个问题是:是否有任何支持像哈希表那样性能的字典式数据结构的prolog呢?
第二个问题是,我意识到由于大多数prolog使用哈希表来存储谓词,我可以编写一个包装谓词的谓词,来断言和撤回事实,从而创建一个利用底层谓词哈希表的字典接口。但是,这个接口会增加开销降低性能吗?
我刚发现:
SWI-Prolog 7版本引入了dicts,作为一个抽象对象具有现代化的语法和功能符号用于访问成员和用户定义的访问函数。
其语法如下:
Tag{Key1:Value1, Key2:Value2, ...}
详细信息请参阅Dicts: structures with named arguments。
需要注意:
point{x:1,y:2}.x
这样的表达式访问字典成员dict
的复合术语。第一个参数是标签。其余参数创建一个排序好的键值对数组。”目前(2019年)实现的操作时间复杂度在 SWI Prolog 手册的“5.4.5:有关字典的实现说明”中给出:
目前,字典表示为使用函数符号为 compound term。其中第一个参数是标签。剩余参数创建了一个已排序的 key-value 数组。
dict
是一个标签,第一个参数是标签名。其余参数创建了一个已排序的key-value对数组表示。这种方式紧凑且保证局部性,查找的时间复杂度为log(N),添加、删除和与其他字典合并的时间复杂度为N。主要缺点在于修改大型字典中的值既费内存也费时间。未来版本可能会在单独结构中共享键或使用二叉树以实现更便宜的更新。其中一个问题是该表示法必须保持规范或者拓展统一性以弥补替代表示方法。
此外
SWI-Prolog字典是内置的SWI-Prolog扩展。另一个选择是
library(assoc)
,通过库提供基于AVL树的映射(因此可以在其他实现中使用)。
library(assoc)
中也使用AVL树。 - Sebastian正如其他人所写的那样,破坏性修改与逻辑编程不兼容,而树库具有巨大的优势,即它们可以用ISO Prolog以纯粹的方式实现,并具有渐进最优的效率。
最后,SWI-Prolog的字典扩展不符合ISO标准,甚至在语法上也不兼容,因此不能移植到符合标准的Prolog系统!请参阅Ulrich Neumerkel的 注释,了解如何以符合ISO标准的方式添加中缀点。