performance - Prolog 性能和递归类型

Question

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

排列方法一:

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(使用内置):

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

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

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

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

方法一:

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

方法二:

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

方法三:

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

因此，非尾递归方法的实时效率要高得多。

在所有其他条件相同的情况下，特定的递归类型是否通常更实时有效(我知道这并不总是一个简单的前提)？这个实验告诉我的是，我可能不想总是为尾递归而努力，但我可能需要先进行性能分析，然后权衡性能优势与尾递归确实具有的其他优势。

Answer 1

真的很好的问题，+1!

尾调用(以及作为特殊情况的尾递归)优化仅适用于谓词是确定性的!此处并非如此，因此无论您以何种顺序放置目标，您的谓词都将始终需要本地堆栈空间。在生成所有解决方案时，非尾递归版本在这里(时间)效率更高，因为它需要对回溯进行更少的统一。

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

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

变体 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).

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

另请注意，我特意保留了原始变量命名和主谓词名称，以避免引入更多变体。就个人而言，我更喜欢通过附加 来明确哪些变量表示列表的命名约定。 s 到他们的名字，类似于普通的英语复数。此外，我更喜欢更清楚地展示(至少是预期的和可取的)代码的声明性、关系性质的谓词名称，并因此建议避免使用命令式名称。

现在考虑展开第一个变体并部分评估它的 3 个元素列表。我们从一个简单的目标开始:

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

然后通过插入permute1/2的定义逐渐展开, 同时明确所有的头部统一。在第一次迭代中，我们得到:

?- 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).

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

?- 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)。

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

从这里可以清楚地看出我们最初可能没有预料到的:一个很大的区别在于头部统一，第一个版本在开始时确定性地执行，而第二个版本执行 一遍又一遍地回溯 .

这个著名的例子很好地表明，与通常的预期有些相反，如果代码不是确定性的，尾递归可能会非常慢。