0

我有一套 DCG 规则（在这种情况下是德语人称代词）：

% personal pronoun (person, case, number, genus)
ppers(1,0,sg,_) --> [ich].
ppers(1,1,sg,_) --> [meiner].
ppers(1,2,sg,_) --> [mir].
ppers(1,3,sg,_) --> [mich].
ppers(2,0,sg,_) --> [du].
ppers(2,1,sg,_) --> [deiner].
ppers(2,2,sg,_) --> [dir].
ppers(2,3,sg,_) --> [dich].
...

因为它们在语义上是相连的，所以通过将它们移动到列表中（例如按人分组）而不是不相关的规则来保留这些信息对我来说是有意义的。这也使事情变得更整洁：

ppers(1,sg,_,[ich, meiner, mir, mich]).
ppers(2,sg,_,[du,deiner,dir,dich]).
...

然后我会选择我想要的项目，我nth0()需要的案例是列表中的索引。

但是，我在跟踪程序时注意到，在检查德语句子的语法是否正确并尝试查找某个部分是否是人称代词时，当我使用上层版本（普通规则）时，Prolog 不会遍历每个实例，但是当我使用下面的列表版本时，将浏览每个列表。

这是否意味着如果我使用列表和 nth0 与普通规则相比，性能会更差？还是 Prolog 跟踪器没有像对列表那样显示对普通规则的爬行？

（我希望我可以使我的问题足够明显，否则我会扩展。）

4

4 回答 4

2

很可能速度和跟踪差异不是由索引（*）引起的，而是由子句头部统一和主体调用 nth 之间的速度和跟踪差异引起的。如果您真的想利用索引并希望在大多数 Prolog 系统中具有可移植性（**），则需要为第一个参数索引重新制定问题。

一种方法是通过附加谓词。假设您最初有这些 DCG 规则：

cat(Attr1, .., Attrn) --> [Terminal1, .., Terminaln].
..

将其转换为：

cat(X1, .., Xn) --> [Y], cat2(Y, X1, .., Xn).

cat2(Terminal1, Attr1, .., Attrn) --> [Terminal2, .., Terminaln].
..

当我们将此应用于您的示例时，我们会得到：

% personal pronoun (person, case, number, genus)
ppers(X1,X2,X3,X4) --> [Y], ppers2(Y,X1,X2,X3,X4).

% personal pronoun 2 (first word, person, case, number, genus)
ppers2(ich,1,0,sg,_) --> [].
ppers2(meiner,1,1,sg,_) --> [].
ppers2(mir,1,2,sg,_) --> [].
ppers2(mich,1,3,sg,_) --> [].
ppers2(du,2,0,sg,_) --> [].
ppers2(deiner,2,1,sg,_) --> [].
ppers2(dir,2,2,sg,_) --> [].
ppers2(dich,2,3,sg,_) --> [].

您可以对代码中的每个类别执行此操作，这是一种词典表。以上工作独立于 DCG 的翻译方式，如果存在第一个参数索引，它将非常快。

再见

(*) 即使您的 Prolog 系统可以进行多参数索引，它可能仍然无法进行复杂的术语索引。为了索引 [ich|X]，Prolog 系统需要下降到列表中，但很可能它不会下降并且只索引 (.)/2，因此所有子句看起来都相同，并且索引没有积极影响。

(**) 我猜 Prolog 系统中唯一与索引有关的共同点是第一个参数索引。除此之外，并非所有的 Prolog 系统都可以将终端放入头部。有些可能在正文中使用 =/2，有些可能在正文中使用 'C'/3。DCG 目前在终端建模方面没有标准化。

于 2012-05-21T13:08:13.393 回答
1

通常，跟踪器会向您展示实际发生的情况，所以是的，如果它迭代替代公式通过匹配直接访问目标术语的位置，那么当您不查看时也会发生这种情况。但要确定这是否真的意味着更差的性能，您必须在真实场景中测量和比较这两种选择。即使跟踪器没有将其显示为单独的步骤，统一也可能会很慢，或者您的运行时系统可能会进行优化甚至编译在trace. 或者它可能会更慢但不足以担心。与往常一样，这里的黄金法则是：先衡量，然后再优化。

于 2012-05-21T10:56:01.397 回答
1

你为什么用nth0？也许可能是性能杀手的罪魁祸首，请改用 memberchk。

除此之外，我认为您对表演的直觉在“参数索引”方面具有良好的背景。DCG 通常用 Prolog 翻译（我在这里使用 SWI-Prolog）：

ppers(1,0,sg,_) --> [ich].

变成

ppers(1, 0, sg, _, [ich|A], A).

最近对 SWI-Prolog 虚拟引擎的优化（我认为）受 YAP 的启发，自动为具有足够绑定参数的谓词构建所有索引。

因此，您可以期望使用您的第一个方案进行解析（使用 SWI-Prolog）会更有效。

以前，只实现了“第一个参数索引”，在这种情况下（或者如果您使用没有索引功能的 Prolog），您应该会发现这些方案之间的时序非常相似。

高温高压

于 2012-05-21T11:19:28.360 回答
0

语法规则被编译成谓词子句，通常被索引。大多数（如果不是全部）Prolog 编译器使用第一个参数索引（默认情况下）来避免在证明目标时尝试永远不会成为证明树一部分的子句。因此，根据您的调用模式，并且正如您使用 Prolog 编译器跟踪支持所观察到的那样，不会单步执行每个谓词子句。此外，使用实例化索引调用 nth0/3 谓词仍然需要对列表进行线性遍历，直到达到指定的索引。与其他人建议的一样，如果您使用 memberchk/2 谓词，则相同。列表就是列表。

于 2012-05-21T20:52:29.690 回答