Prolog递归的顺序是否重要？

Question

我对一个问题的两个解决方案之间的区别有疑问.该问题要求将列表转换为截断列表,如下所示:

?- reduce([a,a,a,b,b,c,c,b,b,d,d],Z).
Z = [a,b,c,b,d].

第一个解决方案需要一个额外的步骤来反转列表:

reduce([X|Xs],Z) :-
   reduce(X,Xs,Y,[X]),
   reverse(Y,Z).

reduce(X,[L|Ls],Y,List) :-
    (  X=L
    -> reduce(X,Ls,Y,List)
    ;  reduce(L,Ls,Y,[L|List])
    ).
reduce(_,[],Y,Y).

第二种解决方案不需要reverse/2:

reduced([X|Xs],Result) :- 
    reduced(Xs,List),
    List=[A|_],
    (  A=X
    -> Result=List
    ;  Result=[X|List]
    ),
    !.
reduced(Result,Result).

在一系列语句之前或之后执行递归时有哪些优化注意事项？条件的顺序是否重要？我倾向于认为提前完成所有递归是要走的路,特别是因为这里需要向后构建列表.

Answer 1

当你优化任何东西时,一定要先测量!(我们大多数人都会忘记这一点....)

优化Prolog时,请注意以下事项:

• 尾递归往往会做得更好(所以你的"一系列陈述之前或之后"问题);
• 避免创建您不需要的选择点(这取决于Prolog实现)
• 使用最佳算法(如果没有,请不要遍历列表两次).

对于或多或少的标准Prolog实现进行"优化"的解决方案看起来可能有点不同.我将其命名list_uniq(类似于命令行uniq工具):

list_uniq([], []). % Base case
list_uniq([H|T], U) :-
    list_uniq_1(T, H, U). % Helper predicate

list_uniq_1([], X, [X]).
list_uniq_1([H|T], X, U) :-
    (   H == X
    ->  list_uniq_1(T, X, U)
    ;   [X|U1] = U,
        list_uniq_1(T, H, U1)
    ).

这是从不同reduce0/2的@CapelliC,因为它使用滞后避免的固有的非确定性[X|Xs],并[X,X|Xs]在第一个参数.

现在声称它是"优化的":

• 它只遍历列表一次(不需要反转)
• 它是尾递归的
• 它不会创建和丢弃选择点

您将获得与@CapelliC相同的12个推论,如果您使用稍长的列表,您将开始看到差异:

?- length(As, 100000), maplist(=(a), As),
   length(Bs, 100000), maplist(=(b), Bs),
   length(Cs, 100000), maplist(=(c), Cs),
   append([As, Bs, Cs, As, Cs, Bs], L),
   time(list_uniq(L, U)).
% 600,006 inferences, 0.057 CPU in 0.057 seconds (100% CPU, 10499893 Lips)
As = [a, a, a, a, a, a, a, a, a|...],
Bs = [b, b, b, b, b, b, b, b, b|...],
Cs = [c, c, c, c, c, c, c, c, c|...],
L = [a, a, a, a, a, a, a, a, a|...],
U = [a, b, c, a, c, b].

用同样的查询reduce0,reduce1,reduce2从@ CapelliC的回答:

% reduce0(L, U)
% 600,001 inferences, 0.125 CPU in 0.125 seconds (100% CPU, 4813955 Lips)
% reduce1(L, U)
% 1,200,012 inferences, 0.393 CPU in 0.394 seconds (100% CPU, 3050034 Lips)
% reduce2(L, U)
% 2,400,004 inferences, 0.859 CPU in 0.861 seconds (100% CPU, 2792792 Lips)

因此,使用cut(!)创建和丢弃选择点也是有代价的.

但是,list_uniq/2就目前而言,第一个参数不是基础的查询可能是错误的:

?- list_uniq([a,B], [a,b]).
B = b. % OK

?- list_uniq([a,A], [a]).
false. % WRONG!

reduce0/2也reduce1/2可能是错的:

?- reduce0([a,B], [a,b]).
false.

?- reduce1([a,B], [a,b]).
false.

至于reduce2/2,我不确定这个:

?- reduce2([a,A], [a,a]).
A = a.

相反,使用的定义if_/3从这样的回答:

list_uniq_d([], []). % Base case
list_uniq_d([H|T], U) :-
    list_uniq_d_1(T, H, U). % Helper predicate

list_uniq_d_1([], X, [X]).
list_uniq_d_1([H|T], X, U) :-
    if_(H = X,
        list_uniq_d_1(T, H, U),
        (   [X|U1] = U,
            list_uniq_d_1(T, H, U1)
        )
    ).

用它:

?- list_uniq_d([a,a,a,b], U).
U = [a, b].

?- list_uniq_d([a,a,a,b,b], U).
U = [a, b].

?- list_uniq_d([a,A], U).
A = a,
U = [a] ;
U = [a, A],
dif(A, a).

?- list_uniq_d([a,A], [a]).
A = a ;
false. % Dangling choice point

?- list_uniq_d([a,A], [a,a]).
false.

?- list_uniq_d([a,B], [a,b]).
B = b.

?- list_uniq_d([a,A], [a,a]).
false.

它需要更长的时间,但谓词似乎是正确的.使用与其他时间相同的查询:

% 3,000,007 inferences, 1.140 CPU in 1.141 seconds (100% CPU, 2631644 Lips)