4

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

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

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

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

4

3 回答 3

6

等一下！在你继续之前，首先测量你的谓词花费的时间！

?- 长度（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 因效率极低而声名狼藉的原因，它阻碍了处理器速度的所有进步。

那么你的程序中发生了什么？无需详细说明，但让我们考虑一下程序的一个小片段（）。虽然这个生成的程序完全无法满足您的目的，但它为我们提供了程序中推理数量的下限：

最大（[X]，X）：-假。
最大([X|Xs],X) :- 最大(Xs,Y), false , X>=Y。
最大（[X|Xs],N）：- 最大（Xs,N），假，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

于 2013-11-12T22:47:42.803 回答
1

尾递归头先解决方案如下所示：

largest( [X|Xs] , Max ) :- largest( Xs , X , Max ) .

largest( []     , R , R ) .
largest( [X|Xs] , T , R ) :- X >  T , largest( Xs , X , R ) .
largest( [X|Xs] , T , R ) :- X =< T , largest( Xs , T , R ) .

largest/2只需调用largest/3，将其累加器播种到列表的头部（初始“最大值”值）。随着largest/3列表向下递归，它会在遇到累加器时用新的“当前”最大值替换该累加器。当列表耗尽时，累加器具有整个列表的最大值。

您的初始解决方案：

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

尾部先行。它递归到列表的末尾，此时它决定列表中的最后一项是初始“最大值”值。当它向上弹出堆栈时，它会将其与前一个值进行比较并执行必要的操作。

您的方法存在两个问题：

  • 它在 O(n 2 ) 时间内运行，因为它必须在每次失败时重复迭代列表。
  • 它消耗堆栈空间，您给出了足够长度的列表，由于您将遇到堆栈溢出，您将无法计算解决方案。

另一方面，尾递归“head-first”方法在 O(n) 时间内运行：列表只迭代一次，最后你就有了解决方案。此外，由于尾递归优化，递归调用本质上转换为迭代，这意味着在初始堆栈帧之外没有消耗任何堆栈空间。这意味着可以为任何长度的列表计算解决方案（前提是您愿意等待答案）。

于 2013-11-13T21:32:08.273 回答
1

惯用的、尾递归的、头先的版本：

largest([X|Xs], O) :- largest(Xs, X, O).

largest([], O, O).
largest([X|Xs], M, O) :-
    M1 is max(X, M),
    largest(Xs, M1, O).
于 2013-11-14T10:18:32.617 回答