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

问题描述

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

这是我目前所拥有的:

最大([X],X).最大([X|Xs]，X):- 最大(Xs，Y)，X>=Y.最大([X|Xs]，N):- 最大(Xs，N)，N>X.

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

解决方案

等一下！在继续之前，请先测量谓词所用的时间！

?- 长度(J，I)，I>10，追加(J，[2]，L)，maplist(=(1)，J)，时间(最大(L，N)).% 12,282 次推断，0.006 秒内 0.006 CPU(99% CPU，1977389 唇)J = [1, 1, 1, 1, 1, 1, 1, 1, 1|...],我 = 11,L = [1, 1, 1, 1, 1, 1, 1, 1, 1|...],N = 2;% 4 次推理，0.000 秒内 0.000 CPU(84% CPU，98697 唇)% 24,570 次推断，0.011 秒内 0.011 CPU(99% CPU，2191568 唇)J = [1, 1, 1, 1, 1, 1, 1, 1, 1|...],我 = 12,L = [1, 1, 1, 1, 1, 1, 1, 1, 1|...],N = 2;% 4 次推断，0.000 CPU 在 0.000 秒内(84% CPU，98556 唇)% 49,146 次推理，0.021 秒内 0.021 CPU(100% CPU，2365986 唇)J = [1, 1, 1, 1, 1, 1, 1, 1, 1|...],我 = 13,L = [1, 1, 1, 1, 1, 1, 1, 1, 1|...],N = 2 ...

长度每增加一，推理的数量显然会增加一倍！这就是 Prolog 因效率极低而声名狼藉的原因，它阻碍了处理器速度的所有进步.

那么您的程序中发生了什么?无需详细说明，但让我们考虑一个小片段(failure-slice) 你的程序.虽然这个生成的程序完全无法满足您的目的，但它为我们提供了程序中推理数量的.最大([X|Xs],X):- 最大(Xs,Y)，false，.最大([X|Xs],N):- 最大(Xs,N)，false，.

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

这是一个可能的重写:

最大([X],X).最大([X|Xs],R):-最大(Xs，Y)，(X＞＝Y，R＝X;Y＞X, R = N).

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

最大([X],X).最大([X|Xs],R):-最大(Xs，Y)，(X＞＝Y-＞R＝X;Y＞X, R = N).

或max/2

最大([X],X).最大([X|Xs],R):-最大(Xs，Y)，R是最大值(X，Y).

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

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

SWI-Prolog:Sum-List

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

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 .largest([X|Xs],X) :- largest(Xs,Y), false, .largest([X|Xs],N) :- largest(Xs,N), false, .

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

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

or 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: Sum-List

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