在下文中,我仅考虑纯Prolog程序。这意味着我不是在谈论副作用和操作系统调用,这些操作和调用使逻辑领域无法在Prolog中进行观察。

有一个众所周知的Prolog程序运行时成本的抽象度量:逻辑推理的数量。我所说的``抽象''是指该措施独立于任何特定的Prolog实现和实际的具体硬件。从某种意义上说,这是一种度量,它为我们提供了有关执行程序所需时间的信息。我们甚至可以通过陈述每秒的推理次数(LIPS)来在某种程度上指定Prolog系统的性能,并且这种方法被广泛使用,可以称之为传统的系统性能指标。传统上,此数字由特定的基准测试,但是“推理数量”的一般概念当然也扩展到其他更复杂的Prolog程序。

但是,据我了解,这种特殊的(敢于说的:具体的)抽象度量并不能在以下重要意义上说明全部事实:

对于任何给定的Prolog目标G,让我们用t(G)表示:T→R在给定的Prolog系统上特定硬件上G的实际执行时间,即从Herbrand项到实数的函数。让我们称量度α:T→R对所有G的真实iff t(G)≈α(G),从某种意义上说,值的差异是一个因数,该因数对于所有目标G和所有“现实”都是常数硬件类型(我必须对最后一点进行说明不足,但为简单起见,在此我假设相同的Prolog实现在``典型''硬件上的执行方式大致相同。我知道实际上并非如此,并且相同实现可能在不同类型的硬件上表现出截然不同的特性。如果是这样,请将定义限制为其中实现“大致”运行相同的硬件类型的子集。)

据我所知,逻辑推理的数量通常不是对Prolog目标实际执行时间的真实衡量,尤其是因为执行统一所需的时间不是由它衡量的。可以构造这样一种情况,即该度量与实际执行时间之间的差异不再受常数限制。

因此,我的问题是:对于Prolog目标的运行时间是否有一个真实的抽象度量?如果通常不存在此措施,请在可以定义这种措施的Prolog程序中指定有意义的子集。例如,通过限制可能发生的统一类型。

例如,在使用Prolog实施智能合约时,此问题具有很高的实际重要性:在这种情况下,即使您的程序在需要达成协议的不同机器上运行,您仍要抽象地衡量运行Prolog程序所花费的时间关于它运行的时间,但是您想保留将来对具体实施技术进行改进的可能性。因此,该措施应仅取决于实际给定的程序,而不取决于实现的任何具体特征,例如所访问的存储单元的数量。

最佳答案

在盛开的here中可以看到复杂性度量的问题。但是嘴唇仍然是有用的度量。您没有得到:

LIPS ~ TIME


但是你得到:

LIPS * DEPTH * COUNT ~ TIME


其中,深度是在运行时对术语深度的度量,它会影响统一的时间成本,计数是子句数量的度量,它会影响统一的数量,包括不会导致推理的失败。

就像您说加法需要一个时间步一样,它的抽象相同,但是实际上我们知道加两个bignum的时间取决于bignum的大小。在这里,术语和子句扮演了bignums的角色。

它有用吗?绝对是的!例如,如果您有两种算法,并且看到深度和计数都相同,则可以用嘴唇进行比较。

07-24 09:38
查看更多