ISO Prolog 谓词的复杂性 [英] Complexity of ISO Prolog predicates

问题描述

标准 Prolog 谓词时间复杂度的上限是否有任何保证?

Are there any guarantees for upper bounds on the time complexity of the standard Prolog predicates?

例如:确定sort(+List, ?SortedList)在O(nlog(n))时间内运行(n是List的长度)在任何符合标准的 Prolog 系统中?

For example: is it certain that sort(+List, ?SortedList) runs in O(nlog(n)) time (n being the length of List) in any standard compliant Prolog system?

推荐答案

tl;dr: No and no.

tl;dr: No and no.

让我们从 sort/2 开始，理想情况下需要 n ld(n) 次比较.很好，但是一次比较需要多长时间?让我们试试这个:

Let's start with sort/2 which ideally would need n ld(n) comparisons. Fine, but how long does one comparison take? Let's try this out:

tails(Es0, [Es0|Ess]) :-
   Es0 = [_|Es],
   tails(Es, Ess).
tails([],[[]]).

call_time(G,T) :-
   statistics(runtime,[T0|_]),
   G,
   statistics(runtime,[T1|_]),
   T is T1 - T0.

| ?- between(12,15,I), N is 2^I, length(L,N),maplist(=(a),L),
     tails(L,LT), call_time(sort(LT,LTs), Tms).

在 SICStus 4.3.1 和 SWI 7.1.28 上

On SICStus 4.3.1 and SWI 7.1.28

I = 12, N = 4096,   Tms_SICS =   680,  Tms_SWI =   3332
I = 13, N = 8192,   Tms_SICS =  2800,  Tms_SWI =  14597
I = 14, N = 16384,  Tms_SICS = 11300,  Tms_SWI =  63656
I = 15, N = 32768,  Tms_SICS = 45680,  Tms_SWI = 315302

通过复制大小，我们可以轻松估计运行时间.如果它也重复，则它是线性的，如果它四倍，则它是二次的.显然两者都至少有二次运行时间.

By duplicating the size we can easily estimate what the runtime will be. If it duplicates as well, it is linear, and if it quadruples it is quadratic. Clearly both have at least quadratic runtime.

以抽象的方式描述精确的运行时间是可能的，但很难确保一切正常.无论如何，在标准文件中强制执行具体的承诺几乎是不可能的.此外，很难验证此类声明.

Describing the precise runtime in an abstract manner might be possible, but it is very difficult to ensure that everything is fine. In any case, it is next-to-impossible to mandate a concrete promise in a standard document. Also, it is very difficult to validate such claims.

最好的抽象度量可能是推理的数量，它们通常很容易观察到.请参阅最大整数或因数.但同样，这只是一个抽象的衡量标准——所以有些东西被撕掉了，抽象.很可能关键功能也被撕掉了.

The best abstract measure might be the number of inferences, often they can be easily observed. See the largest integer or factors. But again, this is only an abstract measure - so something has been torn away, abstraxit. It might very well be the case that the key features have been torn away too.

总的来说，ISO 标准 ISO/IEC 13211-1:1995 核心不强制要求对明显超出范围的运行时复杂性提供任何保证.它在注释中明确提到资源限制也在范围之外:

In general, the ISO standard ISO/IEC 13211-1:1995 core, does not mandate any guarantee for runtime complexities which are clearly out of scope. It mentions explicitly in a note that also resource limits are out of scope:

....

注意—ISO/IEC 13211的这部分没有规定:

NOTE — This part of ISO/IEC 13211 does not specify:

a) Prolog 文本的大小或复杂性将超过
任何特定数据处理系统或语言的能力
处理器，或当相应
超出限制；
...

a) the size or complexity of Prolog text that will exceed the
capacity of any specific data processing system or language
processor, or the actions to be taken when the corresponding
limits are exceeded;
...

永远记住，技术标准是确保系统适用于某些目的的前提.这不是充分条件.请参阅此答案中目的下的示例，了解一个有点极端的示例.

Always remember that a technical standard is a precondition to ensure that a system is fit for some purpose. It is not a sufficient condition. See the example under Purpose in this answer for a somewhat extreme example.

这篇关于ISO Prolog 谓词的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！