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

The number of inferences clearly doubles each time the length increases by one! That's the way how Prolog gets its bad reputation for being extremely inefficient, nixing all progress in processor speed.

So what is happening in your program? There is no need to go into details, but lets consider a small fragment (failure-slice) of your program. While this resulting program is completely dysfunctional for your purpose it gives us a lower bound of the number of inferences in your program:

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

For each element in the list, we have two equally applicable choices. So with a list of N elements, we have 2^N choices!

Here is a possible rewrite:

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