optimization - 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 caselist_uniq([H|T], U) :-    list_uniq_1(T, H, U). % Helper predicatelist_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)    ).

It is different from the reduce0/2 by @CapelliC because it uses lagging to avoid the inherent non-determinism of [X|Xs] and [X,X|Xs] in the first argument.

Now to the claim that it is "optimized":

• It traverses the list exactly once (no need for reversing)
• It it tail-recursive
• It does not create and discard choice points

You will get the same 12 inferences as @CapelliC, and if you then use a somewhat longer list, you will start to see differences:

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

The same query with reduce0, reduce1, reduce2 from @CapelliC's answer:

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

So, creating and discarding choice points with cuts (!) has a price, too.

However, list_uniq/2, as it stands, can be wrong for queries where the first argument is not ground:

?- list_uniq([a,B], [a,b]).B = b. % OK?- list_uniq([a,A], [a]).false. % WRONG!

reduce0/2 and reduce1/2 can be wrong, too:

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

As for reduce2/2, I am not sure about this one:

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

Instead, using the definition of if_/3 from this answer:

list_uniq_d([], []). % Base caselist_uniq_d([H|T], U) :-    list_uniq_d_1(T, H, U). % Helper predicatelist_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)        )    ).

With it:

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

It takes longer, but the predicate seems to be correct.With the same query as used for the other timings:

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