7

データベースに次の事実があるとします。

foo(a, 3).
foo(b, 2).
foo(c, 4).
foo(d, 3).
foo(e, 2).
foo(f, 6).
foo(g, 3).
foo(h, 2).

最小の 2 番目の引数と 2 番目の引数の値を持つすべての最初の引数を収集したいと考えています。初挑戦：

find_min_1(Min, As) :-
    setof(B-A, foo(A, B), [Min-_|_]),
    findall(A, foo(A, Min), As).

?- find_min_1(Min, As).
Min = 2,
As = [b, e, h].

の代わりにsetof/3、次を使用できますaggregate/3。

find_min_2(Min, As) :-
    aggregate(min(B), A^foo(A, B), Min),
    findall(A, foo(A, Min), As).

?- find_min_2(Min, As).
Min = 2,
As = [b, e, h].

注意

これは、数値の最小値を探している場合にのみ同じ結果をもたらします。算術式が含まれている場合、結果は異なる場合があります。数値以外が含まれている場合はaggregate(min(...), ...)、エラーがスローされます!

または、代わりに、キーでソートされた完全なリストを使用できます。

find_min_3(Min, As) :-
    setof(B-A, foo(A, B), [Min-First|Rest]),
    min_prefix([Min-First|Rest], Min, As).

min_prefix([Min-First|Rest], Min, [First|As]) :-
    !,
    min_prefix(Rest, Min, As).
min_prefix(_, _, []).

?- find_min_3(Min, As).
Min = 2,
As = [b, e, h].

最後に、質問に:

  • これをライブラリ(集約)で直接行うことはできますか? 出来るはず…という感じです。

  • std::partition_pointまたは、C++ 標準ライブラリのような述語はありますか?

  • または、これを行う簡単な方法はありますか？

編集：

より説明的になるために。(ライブラリ) 述語があったとしますpartition_point/4:

partition_point(Pred_1, List, Before, After) :-
    partition_point_1(List, Pred_1, Before, After).

partition_point_1([], _, [], []).
partition_point_1([H|T], Pred_1, Before, After) :-
    (   call(Pred_1, H)
    ->  Before = [H|B],
        partition_point_1(T, Pred_1, B, After)
    ;   Before = [],
        After = [H|T]
    ).

(名前は好きじゃないけど、今は我慢できる)

それで：

find_min_4(Min, As) :-
    setof(B-A, foo(A, B), [Min-X|Rest]),
    partition_point(is_min(Min), [Min-X|Rest], Min_pairs, _),
    pairs_values(Min_pairs, As).

is_min(Min, Min-_).

?- find_min_4(Min, As).
Min = 2,
As = [b, e, h].
4

3 に答える 3

1

ライブラリ（集合体）があなたのユースケースをカバーしているとは思いません。集計 (分) は、1 つの証人を許可します。

min(Expr, Witness) min(Min, Witness) という用語。ここで、Min はすべての解に対する Expr の最小バージョンであり、Witness は Min を生成した解に適用されるその他のテンプレートです。複数の解が同じ最小値を提供する場合、Witness は最初の解に対応します。

少し前に、低オーバーヘッドで集約するための述語を備えた小さな「ライブラリ」であるlag.plを作成しました。ユースケースを処理するスニペットを追加しました：

integrate(min_list_associated, Goal, Min-Ws) :-
    State = term(_, [], _),
    forall(call(Goal, V, W),    % W stands for witness
        (    arg(1, State, C),  % C is current min
             arg(2, State, CW), % CW are current min witnesses
             (   ( var(C) ; V @< C )
             ->  U = V, Ws = [W]
             ;   U = C,
                 (   C == V
                 ->  Ws = [W|CW]
                 ;   Ws = CW
                 )
             ),
             nb_setarg(1, State, U),
             nb_setarg(2, State, Ws)
        )),
    arg(1, State, Min), arg(2, State, Ws).

これは、integrate(min) の単純な拡張です...確かに疑わしい比較方法 (同等性のためにあまり一般的な演算子を使用しません) は、代わりにpredsort /3に採用されているような従来の呼び出しを採用する価値があります。効率的には、比較方法を「関数セレクター」のオプションとしてエンコードすることをお勧めします (この場合は min_list_associated)。

状態表現に関連するバグを修正してくれた @false と @Boris に感謝します。を呼び出すnb_setarg(2, State, Ws)と、実際に用語の形が変化しState = (_,[],_)ます。それに応じてgithubリポジトリを更新します...

于 2014-12-08T11:26:22.380 に答える
0

library(pairs)と [ ]を使用するとsort/4、これは次のように簡単に記述できます。

?- bagof(B-A, foo(A, B), Ps),
   sort(1, @=<, Ps, Ss), % or keysort(Ps, Ss)
   group_pairs_by_key(Ss, [Min-As|_]).
Min = 2,
As = [b, e, h].

この への呼び出しsort/4は に置き換えることができますがkeysort/2、sort/4たとえば、最大の 2 番目の引数に関連付けられた最初の引数を見つけることもできます: 2@>=番目の引数として使用するだけです。

このソリューションは、おそらく他のソリューションほど時間とスペースの効率が良くありませんが、理解しやすいかもしれません。

しかし、それを完全に行う別の方法があります。

?- bagof(A, ( foo(A, Min), \+ ( foo(_, Y), Y @< Min ) ), As).
Min = 2,
As = [b, e, h].
于 2015-10-01T06:42:48.897 に答える