Prolog从尾部查找列表中的最大整数

Question

我需要从列表的头部和尾部找到列表中的最大整数.我已经写了一个程序,可以找到最大的头部现在我需要一些帮助从尾部做到这一点.

这是我到目前为止:

largest([X],X).
largest([X|Xs],X) :- largest(Xs,Y), X>=Y.
largest([X|Xs],N) :- largest(Xs,N), N>X.

请记住,这会从头部找到最大的整数,我需要它从尾部开始工作.谢谢您的帮助.

Answer 1

等一下!在继续之前,首先测量谓词所需的时间!

?- length(J,I), I>10, append(J,[2],L),maplist(=(1),J),  time(largest(L,N)).
% 12,282 inferences, 0.006 CPU in 0.006 seconds (99% CPU, 1977389 Lips)
J = [1, 1, 1, 1, 1, 1, 1, 1, 1|...],
I = 11,
L = [1, 1, 1, 1, 1, 1, 1, 1, 1|...],
N = 2 ;
% 4 inferences, 0.000 CPU in 0.000 seconds (84% CPU, 98697 Lips)
% 24,570 inferences, 0.011 CPU in 0.011 seconds (99% CPU, 2191568 Lips)
J = [1, 1, 1, 1, 1, 1, 1, 1, 1|...],
I = 12,
L = [1, 1, 1, 1, 1, 1, 1, 1, 1|...],
N = 2 ;
% 4 inferences, 0.000 CPU in 0.000 seconds (84% CPU, 98556 Lips)
% 49,146 inferences, 0.021 CPU in 0.021 seconds (100% CPU, 2365986 Lips)
J = [1, 1, 1, 1, 1, 1, 1, 1, 1|...],
I = 13,
L = [1, 1, 1, 1, 1, 1, 1, 1, 1|...],
N = 2 ...

每次长度增加1时,推论的数量明显增加一倍!这就是Prolog如何因为效率极低而声名狼借的方式,并且在处理器速度上取得了所有进步.

那么您的计划中发生了什么？没有必要详细介绍,但我们可以考虑一个程序的小片段(失败片).虽然这个结果程序完全不能满足您的目的,但它为我们提供了程序中推理数量的下限:

largest([X],X) :- false.
largest([X|Xs],X) :- largest(Xs,Y), false, X>=Y.
largest([X|Xs],N) :- largest(Xs,N), false, N>X.

对于列表中的每个元素,我们有两个同样适用的选项.所以有了N元素列表,我们有2^N选择!

这是一个可能的重写:

largest([X],X).
largest([X|Xs],R) :-
   largest(Xs,Y),
   (  X>=Y, R = X
   ;  Y > X, R = N
   ).

使用if-then-else可以做得更好......

largest([X],X).
largest([X|Xs],R) :-
   largest(Xs,Y),
   (  X>=Y -> R = X
   ;  Y > X, R = N
   ).

要么 max/2

largest([X],X).
largest([X|Xs],R) :-
   largest(Xs,Y),
   R is max(X,Y).

该程序仍然需要与列表长度成比例的空间.通过使用尾递归版本,您可以将其减少为常量.但至少这个版本现在以线性时间运行.

对于您想要执行的实际优化,请阅读

SWI-Prolog:Sum-List