O(1)项查找

Question

5

我希望在我的当前prolog程序中能够尽快查找术语的存在，而无需prolog引擎遍历所有术语直到它最终到达现有术语。

我没有找到任何证据...但我认为，假定给定

animal(lion).
animal(zebra).
...
% thousands of other animals
...
animal(tiger).

为了确认动物（老虎）在我的prolog数据库中，swi-prolog引擎将不得不浏览数千只动物来尝试与老虎统一。

在其他语言中，我相信HashSet可以解决这个问题，实现O(1)查找......然而，在swi-prolog文档中似乎找不到任何hashsets或hashtables。

是否有适用于hashsets的swi-prolog库，或者是否可以使用term_hash\2自己构建它？

额外信息：我很可能需要在一些动态添加的数据上进行查找，可以使用hashset数据结构或assertz。

- user483036

1

你可能需要注意一些细节。"animal(tiger)" 的时间复杂度为O(1)，但是"animal(X), X=tiger" 的时间复杂度为O(n)。 - repeat

2个回答

2

当内置的第一个参数索引不足时（请注意，一些Prolog系统还提供多参数索引），根据系统，您可以使用内置或库术语哈希谓词构建自己的索引方案。对于ECLiPSe、GNU Prolog、SICStus Prolog、SWI-Prolog和YAP，可以查看term_hash/4谓词的文档。

- Paulo Moura

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mat · Accepted Answer

所有严肃的Prolog系统都通过哈希自动和隐式地执行这种O(1)查找，因此您不必自己执行。

这被称为参数索引，您可以在所有好的Prolog书籍中找到相关解释。还可以在许多Prolog系统（包括SWI）的更新版本中看到“JIT（即时）索引”。索引也适用于动态添加的子句，这是assertz/1速度变慢的原因之一，因此不适合数据更改频率高于读取频率的情况。

您还可以通过创建具有越来越多事实的数据库并查看参数索引应用时查找时间保持大致恒定来轻松测试此功能。