Prolog性能和递归类型 [英] Prolog performance and recursion type

问题描述

我在几个程序中玩permutation，偶然发现了这个小实验:

I was playing with permutation in a couple of programs and stumbled upon this little experiment:

排列方法1:

permute([], []).
permute([X|Rest], L) :-
    permute(Rest, L1),
    select(X, L, L1).

排列方法2:

permute([], []).
permute(L, [P | P1]) :-
    select(P, L, L1),
    permute(L1, P1).

排列方法3(使用内置方法):

Permutation method 3 (use the built-in):

permute(L, P) :- permutation(L, P).

我知道使用尾递归是一种很好的做法，通常使用内置函数是有效的.但是当我运行以下命令时:

I understand that it's good practice to use tail recursion, and generally using built-ins is supposed to be efficient. But when I run the following:

time(findall(P, permute([1,2,3,4,5,6,7,8,9], P), L)).

我得到以下结果，这些结果在几次运行中相对一致:

I got the following results, which are relatively consistent across several runs:

方法1:

% 772,064 inferences, 1.112 CPU in 2.378 seconds (47% CPU, 694451 Lips)

方法2:

% 3,322,118 inferences, 2.126 CPU in 4.660 seconds (46% CPU, 1562923 Lips)

方法3:

% 2,959,245 inferences, 1.967 CPU in 4.217 seconds (47% CPU, 1504539 Lips)

因此，非尾递归方法的实时性要高得多.

So the non-tail recursive method is quite significantly more real-time efficient.

在其他所有条件都相同的情况下，特定的递归类型通常更具实时性吗(我知道这并不总是一个简单的前提)?该实验告诉我的是，我可能不希望一直追求尾递归，但是我可能需要先进行性能分析，然后再权衡性能收益与尾递归所具有的其他好处.

Is a particular recursion type generally more real time efficient, all other things being equal (I know that's not always a simple premise)? What this experiment tells me is that I may not want to be always striving for tail recursion, but I may need to do a performance analysis first, then weigh performance benefit against other benefits that tail recursion does have.

推荐答案

非常好的问题，+ 1！

Really nice question, +1!

尾部调用(在特殊情况下，尾部递归)优化仅在谓词为确定性时才适用！这里不是这种情况，因此您的谓词将始终需要本地堆栈空间，无论您按什么顺序放置目标.非尾递归版本在生成所有解决方案时效率更高(时间)，因为它需要在回溯上进行更少的统一.

Tail call (and, as a special case, tail recursion) optimization only applies if the predicate is deterministic! This is not the case here, so your predicate will always require the local stack space, no matter in which order you place the goals. The non-tail recursive version is more (time-)efficient here when generating all solutions because it needs to do fewer unifications on backtracking.

编辑:我正在扩展这一点，因为值得更详细地研究性能差异.

EDIT: I am expanding on this point since it is well worth studying the performance difference in more detail.

首先，为清楚起见，我将两个不同的版本重命名以明确说明我在谈论哪个版本:

First, for clarity, I rename the two different versions to make clear which version I am talking about:

变体1 :非尾递归:

permute1([], []).
permute1([X|Rest], L) :-
    permute1(Rest, L1),
    select(X, L, L1).

变体2 :尾递归:

permute2([], []).
permute2(L, [P|P1]) :-
    select(P, L, L1),
    permute2(L1, P1).

再次请注意，尽管第二个版本显然是尾部递归的，但是尾部调用(以及尾部递归)优化仅在谓词是<确定性> 时才有用.当我们生成所有排列时，这无济于事，因为在这种情况下仍会留下选择点.

Note again that, although the second version is clearly tail recursive, tail call (and hence also tail recursion) optimisation only helps if the predicate is deterministic, and hence cannot help when we generate all permutations, because choice points are still left in that case.

还请注意，我故意保留了原始变量的命名和主谓词名称，以避免引入更多的变体.就个人而言，我更喜欢使用一种命名约定，该命名约定通过在名称的名称后附加一个 s 来明确表示 lists 的变量，这类似于常规的英语复数形式.另外，我更喜欢谓词名称，使其更清楚地表现出代码的(至少是预期的和合意的)声明性，关系性质，并出于这个原因，建议避免使用命令性名称.

Note also that I am deliberately retaining the original variable naming and main predicate name to avoid introducing more variants. Personally, I prefer a naming convention that makes clear which variables denote lists by appending an s to their names, in analogy to regular English plural. Also, I prefer predicate names that more clearly exhibit the (at least intended and desirable) declarative, relational nature of the code, and recommend to avoid imperative names for this reason.

现在考虑展开第一个变体，并对其中的三个元素进行部分评估.我们从一个简单的目标开始:

Consider now unfolding the first variant and partially evaluating it for a list of 3 elements. We start with a simple goal:

?- Xs = [A,B,C], permute1(Xs, L).

，然后通过插入permute1/2的定义逐步将其展开，同时使所有磁头统一明确.在第一次迭代中，我们获得:

and then gradually unfold it by plugging in the definition of permute1/2, while making all head unifications explicit. In the first iteration, we obtain:

?- Xs = [A,B,C], Xs1 = [B,C], permute1(Xs1, L1), select(A, L, L1).

我用粗体标记了头部的统一.

I am marking the head unifications in bold.

现在，剩下permute1/2的一个目标.因此，我们重复该过程，再次插入谓词唯一适用的规则主体来代替其头部:

Now, still one goal of permute1/2 is left. So we repeat the process, again plugging in the predicate's only applicable rule body in place of its head:

?- Xs = [A,B,C], Xs1 = [B,C], Xs2 = [C], permute1(Xs2, L2), select(B, L1, L2), select(A, L, L1).

再通过一次，我们得到:

One more pass of this, and we obtain:

?- Xs = [A,B,C], Xs1 = [B,C], Xs2 = [C], select(C, L2, []), select(B, L1, L2), select(A, L, L1).

如果我们反复展开permute1/2的定义，这就是原始目标.

This is what the original goal looks like if we just unfold the definition of permute1/2 repeatedly.

现在，第二个变体呢?同样，我们从一个简单的目标开始:

Now, what about the second variant? Again, we start with a simple goal:

?- Xs = [A,B,C], permute2(Xs, Ys).

展开permute2/2的一次迭代将产生等效的版本:

One iteration of unfolding permute2/2 yields the equivalent version:

?- Xs = [A,B,C], Ys = [P|P1], select(P, Xs, L1), permute2(L1, P1).

和第二次迭代产生:

?- Xs = [A,B,C], Ys = [P|P1], select(P, Xs, L1),  Ys1 = [P1|P2], select(P1, L1, L2), permute2(L2, P2).

我将第三次也是最后一次迭代作为一个简单的练习，我强烈建议您这样做.

I leave the third and last iteration as a simple exercise that I strongly recommend you do.

从这一点很明显我们最初可能没有想到:头部统一有很大的不同，第一个版本在开始时就确定地执行，第二个版本在开始时就确定地执行. 一遍又一遍的回溯.

And from this it is clear what we initially probably hadn't expected: A big difference lies in the head unifications, which the first version performs deterministically right at the start, and the second version performs over and over on backtracking.

这个著名的例子很好地表明，与代码的一般预期相反，如果代码不是确定性的，尾部递归的速度可能会很慢.

This famous example nicely shows that, somewhat contrary to common expectation, tail recursion can be quite slow if the code is not deterministic.

这篇关于Prolog性能和递归类型的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！