Prolog性能和递归类型

Question

我正在玩permutation几个程序,并偶然发现了这个小实验:

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

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

我知道使用尾递归是一种好习惯,通常使用内置函数应该是有效的.但是当我运行以下内容时:

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

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

方法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)

因此,非尾递归方法非常实时有效.

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

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

我正在用粗体标记头部统一.

现在,还permute1/2剩下一个目标.所以我们重复这个过程,再次插入谓词唯一适用的规则体代替它的头部:

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

再过一次,我们得到:

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

如果我们只permute1/2重复展开反复定义,这就是原始目标的样子.

现在,第二个变种怎么样？同样,我们从一个简单的目标开始:

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

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

从这一点可以清楚地看出我们最初可能没有预料到的情况:一个重要的区别在于头部统一,第一个版本在开始时确定性地执行,第二个版本在回溯上反复执行.

这个着名的例子很好地表明,如果代码不是确定性的,那么与常见的期望有些相反,尾递归可能会非常慢.