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)

方法二：

% 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和2不会在第一个参数空闲时终止，而方法3会。

无论如何，方法1似乎真的比内置的高效得多。很高兴知道。

编辑:考虑到库实现只是调整参数的实例化并调用方法1，我将在SWI-Prolog邮件列表上讨论你的方法2作为替代方法(或者，你更喜欢自己做，让我知道)。

更多编辑:我之前忘了指出，排列/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 doc page上发表了关于这个主题的评论。

Answer 2

我怀疑引发这项调查的是the discussion about tail-recursive sum/2 using an accumulator还是不是。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时必须注意的权衡之一。很难让谓词对所有人都适用，并且总是执行得很好；您必须决定哪些是“特权路径”，哪些不是。

我依稀记得最近有人展示了一个附加列表“在返回期间”的例子，以及你如何使用不是或不应该是尾递归的东西，并使其工作，这要归功于统一，但我手头没有这个链接。希望是谁上次提出来的(会吗？)将会出现并分享它。

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

Answer 3

很好的例子。但我更喜欢使用，它不会在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比permute3/2更少执行LCO的情况。

也就是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中花费了更多的时间。