11

X私はすべてを数える必要がありsome_predicate(X)、そのようなものは本当にたくさんありXます。それを行う最善の方法は何ですか？

最初の手がかりはfindall、リストに蓄積し、リストの長さを返すことです。

countAllStuff( X ) :-
    findall( Y
           , permutation( [1,2,3,4,5,6,7,8,9,10], Y )
           , List
           ),
    length( List, X ).

(permutation/2多くの結果があり、カウントを計算する方法が悪いことを示すダミーのプレースホルダーです)

明らかに、実際のデータではスタック オーバーフローが発生します。

?- countAllStuff( X ).
ERROR: Out of global stack

次に、 に置き換えようとしてfindallいsetofますが、役に立ちません。

最後に、aggregate述語の [ ][1] (クリック可能) ファミリを見つけて、 and を使用しようとしましaggregate/3たaggregate/4。

?- aggregate(count, permutation([1,2,3,4], X), Y ).
X = [1, 2, 3, 4],
Y = 1 .

?- aggregate(count, [1,2,3,4], permutation([1,2,3,4], X), Y ).
X = [1, 2, 3, 4],
Y = 1 ;
X = [1, 2, 4, 3],
Y = 1 ;

それはすべて間違っていると思います。私はこのようなものを取得する必要があります:

?- aggregate(count, permutation([1,2,3,4], X), Y ).
Y = 24 .

  1. 私は何を間違っていますか？

  2. 正しい答えを計算する述語を宣言するにはどうすればよいですか? [1]: http://www.swi-prolog.org/pldoc/doc/home/vnc/prolog/lib/swipl/library/aggregate.pl

4

4 に答える 4

12

のように、存在量化された変数を使用しますsetof。

?- aggregate(count, X^permutation([1,2,3,4], X), N).
N = 24.
于 2011-05-08T21:13:30.953 に答える
7

SWI-Prolog には、グローバル ストアのロックを回避する、より効率的なバージョンがあります。したがって、nb_setval と nb_getval を使用するだけで、少なくとも 3 倍のパフォーマンスが得られます (マルチスレッドの場合)。少し前に、別の質問が解の数え方に関するものでした。アグリゲーションのベースであるため、Prolog を学習する際の明らかなストップ ポイントです。これらのモノスレッドの意味的に同等の呼び出しを使用して得られる効率の向上を評価するには、次のようにします。

count_solutions(Goal, N) :-
assert(count_solutions_store(0)),
repeat,
(   call(Goal),
    retract(count_solutions_store(SoFar)),
    Updated is SoFar + 1,
    assert(count_solutions_store(Updated)),
    fail
;   retract(count_solutions_store(N))
), !.
:- dynamic count_solutions_store/1.

% no declaration required here
count_solutions_nb(Goal, N) :-
    nb_setval(count_solutions_store, 0),
    repeat,
    (   call(Goal),
        nb_getval(count_solutions_store, SoFar),
        Updated is SoFar + 1,
        nb_setval(count_solutions_store, Updated),
        fail
    ;   nb_getval(count_solutions_store, N)
    ), !.

parent(jane,dick).
parent(michael,dick).
parent(michael,asd).

numberofchildren(Parent, N) :-
    count_solutions_nb(parent(Parent, _), N).

many_solutions :-
    between(1, 500000, _).

time_iso :-
    time(count_solutions(many_solutions, N)),
    write(N), nl.

time_swi :-
    time(count_solutions_nb(many_solutions, N)),
    writeln(N).

私のシステムでは、私は得る

?- [count_sol].
% count_sol compiled 0,00 sec, 244 bytes
true.

?- time_iso.
tim% 1,000,006 inferences, 2,805 CPU in 2,805 seconds (100% CPU, 356510 Lips)
500000
true.

?- time_swi.
% 2,000,010 inferences, 0,768 CPU in 0,768 seconds (100% CPU, 2603693 Lips)
500000
true.
于 2011-09-27T15:11:06.000 に答える
4

もありますaggregate_all/3：

?- aggregate_all(count, permutation([1, 2, 3, 4], _), Total).
Total = 24.

ただし、実行時とスタックのオーバーフローに関する限り、findall+lengthソリューションと同じように機能するようです。

?- N is 10^7, time(aggregate_all(count, between(1, N, _), Total)).
% 10,000,022 inferences, 5.075 CPU in 5.089 seconds (100% CPU, 1970306 Lips)
N = Total, Total = 10000000.

?- N is 10^7, time((findall(X, between(1, N, _), L), length(L, Total))).
% 10,000,013 inferences, 4.489 CPU in 4.501 seconds (100% CPU, 2227879 Lips)
N = 10000000,
L = [_G30000569, _G30000566, _G30000545|...],
Total = 10000000.

?- N is 10^8, aggregate_all(count, between(1, N, _), Total).
ERROR: Out of global stack

?- N is 10^8, findall(X, between(1, N, _), L), length(L, Total).
ERROR: Out of global stack

assert/を使用して解を数えることができますretract。これは非常に遅いですが、「スタック不足」の問題を回避します。

?- assert(counter(0)), N is 10^8, between(1, N, _),
   retract(counter(C)), C1 is C + 1, assert(counter(C1)), fail
   ; retract(counter(C)).
C = 100000000.
于 2011-05-08T21:14:01.690 に答える