Prolog从尾部查找列表中的最大整数 [英] Prolog finding the largest integer in a list from the tail

问题描述

我需要从列表的开头或结尾查找列表中的最大整数.我已经编写了一个程序，可以从头开始查找最大的程序，现在我需要一些帮助来从头开始查找程序.

I need to find the largest integer in a list from the head of a list and alternatively from the tail. I have already written a program that can find the largest from the head now I need some help to do it from the tail.

这是我到目前为止所拥有的:

Here is what I have so far:

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

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

Keep in mind that this finds the largest integer from the head, and I need it to work from the tail. Thanks for the help.

推荐答案

请稍等片刻！在继续之前，请先测量谓词花费的时间！

Hold on for a second! Before you continue, first measure the time your predicate takes!

?- 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如何因效率极低而臭名昭著，从而阻碍了处理器速度的所有进步.

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.

对于列表中的每个元素，我们有两个同样适用的选择.因此，有了N个元素的列表，我们就有了2^N个选择！

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

这里是可能的重写:

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

通过使用if-then-else，您甚至可以做得更好...

You can do even better by using 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).

此程序仍然需要与列表长度成比例的空间.通过使用尾部递归版本，可以将其减少为常数.但是至少此版本现在可以线性运行.

This program still requires space proportional to the length of the list. And that is what you can reduce to a constant, by using a tail-recursive version. But at least this version runs now in linear time.

有关要执行的实际优化，请阅读

And for the actual optimization you want to perform, read

SWI-Prolog:汇总列表

这篇关于Prolog从尾部查找列表中的最大整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！