11

我在玩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)

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

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

4

4 回答 4

7

非常好的问题，+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​​] , 选择(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)。

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

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

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

于 2013-06-10T06:21:48.147 回答
4

真的很好的问题。

等待某人发布时间/空间分析，我可以提供的唯一警告是方法 1 和 2 在第一个参数空闲时不会终止，而方法 3 会。

无论如何，方法 1 似乎确实比内置方法更有效。很高兴知道。

编辑：鉴于库实现仅调整参数的实例化并调用方法 1，我将在 SWI-Prolog 邮件列表中讨论您的方法 2 作为替代方法（或者，您更喜欢自己做，让我知道）。

更多编辑：我之前忘记指出 permutation/3 （比如说，方法 2）给出了按字典顺序排列的解决方案，而方法 1 没有。我认为这可能是一个强烈的优先要求，但考虑到方法 1 允许的性能提升，应该将其表示为一个选项。

?- time(call_nth(permute1([0,1,2,3,4,5,6,7,8,9],P),1000000)).
% 3,112,758 inferences, 3,160 CPU in 3,162 seconds (100% CPU, 984974 Lips)
P = [1, 4, 8, 3, 7, 6, 5, 9, 2|...] .

?- time(call_nth(permute2([0,1,2,3,4,5,6,7,8,9],P),1000000)).
% 10,154,843 inferences, 9,779 CPU in 9,806 seconds (100% CPU, 1038398 Lips)
P = [2, 7, 8, 3, 9, 1, 5, 4, 6|...] .

YAP 带来更多收益！

?- time(call_nth(permute1([0,1,2,3,4,5,6,7,8,9],P),1000000)).
% 0.716 CPU in 0.719 seconds ( 99% CPU)
P = [1,4,8,3,7,6,5,9,2,0]

?- time(call_nth(permute2([0,1,2,3,4,5,6,7,8,9],P),1000000)).
% 8.357 CPU in 8.368 seconds ( 99% CPU)
P = [2,7,8,3,9,1,5,4,6,0]

编辑：我在 SWI-Prolog文档页面上发表了关于这个主题的评论。

于 2013-06-10T05:21:24.613 回答
4

我怀疑引发这次调查的原因是关于使用累加器的尾递归与不sum/2使用累加器的讨论。这个sum/2例子非常简单。一个版本在堆栈上进行算术运算，另一个版本使用累加器。然而，就像现实世界中的大多数事情一样，一般的事实是“视情况而定”。例如，比较方法 1 和 2 使用完全实例化的效率：

?- time(permute([1,2,3,4,5,6,7,8,9], [1,2,3,4,5,6,7,8,9])).
% 18 inferences, 0.000 CPU in 0.000 seconds (66% CPU, 857143 Lips)
true ;
% 86,546 inferences, 0.022 CPU in 0.022 seconds (100% CPU, 3974193 Lips)
false.

?- time(permute([1,2,3,4,5,6,7,8,9], [1,2,3,4,5,6,7,8,9])).
% 18 inferences, 0.000 CPU in 0.000 seconds (62% CPU, 857143 Lips)
true ;
% 47 inferences, 0.000 CPU in 0.000 seconds (79% CPU, 940000 Lips)
false.

当您生成解决方案（如在您的测试中）时，方法 1 优于方法 2，但当您只是检查时，方法 2 优于方法 1。查看代码很容易看出原因：第一个必须重新排列列表的整个尾部，而第二个只需尝试选择一个项目。在这种情况下，可能很容易指出生成案例并说它更需要。这种确定只是在处理 Prolog 时必须跟踪的权衡之一。做出对所有人都适用并且总是表现出色的谓词是非常困难的；您必须决定哪些是“特权路径”，哪些不是。

我确实隐约记得最近有人展示了一个“在返回期间”附加列表的示例，以及如何采用不是或不应该是尾递归的东西并通过统一使其工作，但我没有链接便利。希望上次提出它的人（Will？）会出现并分享它。

顺便说一句，好问题。您的调查方法是有效的，您只需要考虑其他实例化模式。就我个人而言，我通常会更加担心正确性和通用性，而不是预先考虑性能。如果我立即看到如何使用累加器，我会的，但否则我不会那样做，直到我真正需要更好的性能。尾递归只是提高性能的一种方法；经常有其他事情需要处理得不好或更糟。

于 2013-06-10T05:38:19.557 回答
0

很好的例子。但我宁愿使用，它不会在 permute([], []) 中留下选择点：

permute3([], []). 
permute3([H|T], [P|P1]) :- 
    select(P, [H|T], L1), 
    permute3(L1, P1).

它的尾递归比 permute2/2 快 20%，但仍然没有 permute1/2 快。

?- time((permute2([1,2,3,4,5,6,7,8,9,0],_), fail; true)).
% 29,592,302 inferences, 1.653 CPU in 1.667 seconds (99% CPU, 17896885 Lips)
true.

?- time((permute3([1,2,3,4,5,6,7,8,9,0],_), fail; true)).
% 25,963,501 inferences, 1.470 CPU in 1.480 seconds (99% CPU, 17662390 Lips)
true.

但我不确定mat的解释是否正确。也可能是 permute1/2 执行 LCO 的频率低于 permute3/2。

即n! 子调用 permute1/2 的结果，只有最后一次重做不会留下选择点。另一方面，在 permute3/2 中，每个 select/3 调用都有 n 个结果并且没有

在最后的重做中留下一个选择点。我做了一个小测试，为每个 LCO 写一个句号：

?- permute1([1,2,3],_), fail; nl.
...
?- permute3([1,2,3],_), fail; nl.
..........

LCO 在故障循环中没有什么特别的好处。但是 Prolog 系统不知道它。所以我想这就是花费不必要的时间的地方，在 permute3/2 中花费更多。

于 2020-05-31T15:13:18.507 回答