Prolog 性能和递归类型 [英] Prolog performance and recursion type
问题描述
我在几个程序中使用 permutation 并偶然发现了这个小实验:
排列方式一:
置换([], []).置换([X|Rest]，L):-置换(休息，L1)，选择(X，L，L1).排列方法二:
置换([], []).置换(L，[P | P1]):-选择(P，L，L1)，置换(L1，P1).排列方式3(使用内置):
permute(L, P) :- 置换(L, P).我知道使用尾递归是一种很好的做法，而且通常使用内置函数应该是有效的.但是当我运行以下命令时:
时间(findall(P, permute([1,2,3,4,5,6,7,8,9], P), L)).我得到了以下结果，在几次运行中都比较一致:
方法一:
% 772,064 次推理，1.112 CPU 在 2.378 秒内(47% CPU，694451 唇)方法二:
% 3,322,118 次推理，2.126 CPU 在 4.660 秒内(46% CPU，1562923 唇)方法三:
% 2,959,245 推理，1.967 CPU 在 4.217 秒内(47% CPU，1504539 唇)因此，非尾递归方法的实时效率要高得多.
在所有其他条件相同的情况下，特定的递归类型通常是否更实时有效(我知道这并不总是一个简单的前提)?这个实验告诉我的是，我可能不想一直追求尾递归，但我可能需要先进行性能分析，然后权衡性能优势与尾递归确实具有的其他优势.
非常好的问题，+1！
尾调用(以及，作为一种特殊情况，尾递归)优化仅适用于谓词确定性！这不是这里的情况，所以你的谓词总是需要本地堆栈空间，无论你以什么顺序放置目标.在生成所有解决方案时，非尾递归版本在这里更(时间)效率更高，因为它需要在回溯上做更少的统一.
编辑:我正在扩展这一点，因为值得更详细地研究性能差异.
首先，为了清楚起见，我重命名了两个不同的版本，以明确我说的是哪个版本:
变体 1:非尾递归:
permute1([], []).permute1([X|Rest], L) :-permute1(休息，L1)，选择(X，L，L1).变体 2:尾递归:
permute2([], []).permute2(L, [P|P1]) :-选择(P，L，L1)，置换2(L1，P1).再次注意，虽然第二个版本显然是尾递归的，但尾调用(因此也是尾递归)优化仅在谓词是确定性时才有帮助，因此当我们生成所有排列时无济于事，因为在这种情况下仍然会留下选择点.
还请注意，我故意保留原始变量命名和主要谓词名称以避免引入更多变体.就个人而言，我更喜欢一种命名约定，通过在名称后面附加 s 来明确哪些变量表示 lists，类似于常规的英语复数.此外，我更喜欢更清楚地展示代码的(至少是预期的和可取的)声明性、关系性质的谓词名称，因此建议避免使用命令性名称.
<小时>现在考虑展开第一个变体并部分评估它以获得 3 个元素的列表.我们从一个简单的目标开始:
?- Xs = [A,B,C], permute1(Xs, L).然后通过插入 permute1/2 的定义逐渐展开它，同时明确所有头部统一.在第一次迭代中，我们得到:
我用粗体标记头部统一.
现在，还剩下一个permute1/2的目标.所以我们重复这个过程，再次插入谓词的唯一适用规则体来代替它的头部:
再通过一次，我们得到:
<上一页>?- Xs = [A,B,C], Xs1 = [B,C], Xs2 = [C], select(C, L2, []), select(B, L1, L2)，选择(A，L，L1).如果我们只是重复展开 permute1/2 的定义，这就是最初的目标.
现在，第二个变种呢?同样，我们从一个简单的目标开始:
?- Xs = [A,B,C], permute2(Xs, Ys).展开 permute2/2 的一次迭代产生等效版本:
第二次迭代产生:
<上一页>?- Xs = [A,B,C], Ys = [P|P1], 选择(P, Xs, L1), Ys1 = [P1|P2]，选择(P1，L1，L2)，置换2(L2，P2).我将第三次也是最后一次迭代作为一个简单的练习，我强烈建议你这样做.
<小时>从这里可以清楚地看出我们最初可能没有预料到:一个很大的区别在于 head 统一，第一个版本在开始时就确定性地执行，而第二个版本执行一遍又一遍地回溯.
这个著名的例子很好地表明，如果代码不是确定性的，尾递归可能会非常慢.
I was playing with permutation in a couple of programs and stumbled upon this little experiment:
Permutation method 1:
permute([], []).
permute([X|Rest], L) :-
permute(Rest, L1),
select(X, L, L1).
Permutation method 2:
permute([], []).
permute(L, [P | P1]) :-
select(P, L, L1),
permute(L1, P1).
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:
Method 1:
% 772,064 inferences, 1.112 CPU in 2.378 seconds (47% CPU, 694451 Lips)
Method 2:
% 3,322,118 inferences, 2.126 CPU in 4.660 seconds (46% CPU, 1562923 Lips)
Method 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.
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:
Variant 1: Non-tail recursive:
permute1([], []).
permute1([X|Rest], L) :-
permute1(Rest, L1),
select(X, L, L1).
Variant 2: Tail-recursive:
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.
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).
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.
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).
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).
One iteration of unfolding permute2/2 yields the equivalent version:
?- Xs = [A,B,C], Ys = [P|P1], select(P, Xs, L1), permute2(L1, P1).
and a second iteration yields:
?- 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屋！
