3

GNU Prolog にこのコードがありますが、50 要素のペアリストでなぜ遅いのかわかりません。

pairwise_min( [X], X ) :- !.
pairwise_min( [(A,B)|T], (A,B) ) :-
    pairwise_min( T, (_,B1) ),
    B1 > B,
    !.
pairwise_min( [(_,B)|T], (A1,B1) ) :-
    pairwise_min( T, (A1,B1) ),
    B1 =< B,
    !.

次のクエリには 10 秒かかります。

?- pairwise_min( [(25,25),(24,24),(23,23),(22,22),(21,21),(20,20),(19,19),(18,18),(17,17),(16,16),(15,15),(14,14),(13,13),(12,12),(11,11),(10,10),(9,9),(8,8),(7,7),(6,6),(5,5),(4,4),(3,3),(2,2),(1,1)], X ).

この最小値をすばやく見つけるにはどうすればよいですか?

4

3 に答える 3

4

トレースすると、問題をすぐに確認できます。

?- trace, pairwise_min( [(25,25),(24,24),(23,23),(22,22),(21,21),(20,20),(19,19),(18,18),(17,17),(16,16),(15,15),(14,14),(13,13),(12,12),(11,11),(10,10),(9,9),(8,8),(7,7),(6,6),(5,5),(4,4),(3,3),(2,2),(1,1)], X ).
   Call: (7) pairwise_min([ (25, 25), (24, 24), (23, 23), (22, 22), (21, 21), (20, 20), (19, 19), (..., ...)|...], _G737) ? 
   ... snip ...
   Call: (30) pairwise_min([ (2, 2), (1, 1)], (_G1065, _G1066)) ? 
   Call: (31) pairwise_min([ (1, 1)], (_G1068, _G1069)) ? 
   Exit: (31) pairwise_min([ (1, 1)], (1, 1)) ? 
   Call: (31) 1>2 ? 
   Fail: (31) 1>2 ? 
   Redo: (30) pairwise_min([ (2, 2), (1, 1)], (_G1065, _G1066)) ? 
   Call: (31) pairwise_min([ (1, 1)], (_G1065, _G1066)) ? 
   Exit: (31) pairwise_min([ (1, 1)], (1, 1)) ? 
   Call: (31) 1=<2 ? 
   Exit: (31) 1=<2 ? 
   Exit: (30) pairwise_min([ (2, 2), (1, 1)], (1, 1)) ? 
   Call: (30) 1>3 ? 
   Fail: (30) 1>3 ? 
   Redo: (29) pairwise_min([ (3, 3), (2, 2), (1, 1)], (_G1062, _G1063)) ? 
   Call: (30) pairwise_min([ (2, 2), (1, 1)], (_G1062, _G1063)) ? 
   Call: (31) pairwise_min([ (1, 1)], (_G1068, _G1069)) ? 
   Exit: (31) pairwise_min([ (1, 1)], (1, 1)) ? 
   Call: (31) 1>2 ? 
   Fail: (31) 1>2 ? 
   Redo: (30) pairwise_min([ (2, 2), (1, 1)], (_G1062, _G1063)) ? 
   Call: (31) pairwise_min([ (1, 1)], (_G1062, _G1063)) ? 
   Exit: (31) pairwise_min([ (1, 1)], (1, 1)) ? 
   Call: (31) 1=<2 ? 
   Exit: (31) 1=<2 ?

基本的に、問題は、2 番目のケースで違いはありませんが、両方のケースでpairwise_min(T, ...)呼び出しを終了することです。テールのペアごとの最小値は、現在の要素がそれに対してチェックアウトする方法に関係なく、テールのペアごとの最小値です。

適切な解決策は、次のような明示的な条件を使用して 2 番目の規則を削除することです。

pairwise_min( [X], X ) :- !.
pairwise_min( [(A,B)|T], (RA,RB) ) :-
    pairwise_min(T, (A1,B1)), !,
    (B1 > B -> (RA = A,  RB = B)
             ; (RA = A1, RB = B1)).

私にとって読みやすさに対する重大な障害は、ペアごとの最小値で達成しようとしている順序の種類を実際に把握していないことです。しかし、とにかくそれを独自の述語に抽出することは、将来にとって良い考えです。私はあなたの最低限の権利を得たという自信がありません。あなたが望むことをするのは真実で@</2はありませんか？その場合は、非常にタイトな末尾再帰的な折り畳みでこれを行うことができます。

minimum([X|Xs], Min) :- minimum(Xs, X, Min).
minimum([], Min, Min).
minimum([X|Xs], MinSoFar, Min) :-
    (X @< MinSoFar -> minimum(Xs,        X, Min)
                    ; minimum(Xs, MinSoFar, Min)).

そうでない場合は、min_pair/22 つのペアを比較する独自の述語を作成し、代わりにそれを使用し@</2て利点を得ることができます。または、上記の改訂版から呼び出してpairwise_min/2、末尾呼び出しの最適化の利点を確認してください。

このバージョンのパフォーマンスを向上させるには、多少問題があると思います。

于 2013-12-04T23:47:03.570 に答える
2

非常に単純な定義で、最適化されていませんがかなり高速です

pairwise_min(L, (A,B)) :-
    select((A,B), L, R),
    \+ ( member((A1,B1), R), B1 < B ).

とにかく、コードのパフォーマンスを調べることは、Prolog の実行モデルを理解するための非常に良い方法です。

于 2013-12-05T00:24:34.657 に答える