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

ちょっと待って！続行する前に、まず述語にかかる時間を測定してください。

?- length(J,I), I>10, append(J,[2],L),maplist(=(1),J), time(largest(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 秒で 0.000 CPU (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 ...

長さが 1 増加するたびに、推論の数は明らかに 2 倍になります。これが、プロローグが非常に非効率的であるという悪い評判を得る方法であり、プロセッサ速度のすべての進歩を台無しにします.

では、あなたのプログラムでは何が起こっているのでしょうか? 詳細に入る必要はありませんが、プログラムの小さな断片 ( この結果のプログラムは目的に対して完全に機能不全ですが、プログラム内の推論数の下限を示します。

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

リスト内の各要素について、2 つの等しく適用可能な選択肢があります。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 に答える