агрегат / 3 в swi-прологе - PullRequest
Новая
       10

агрегат / 3 в swi-прологе

10 голосов

Мне нужно посчитать все X, что some_predicate(X), а таких X действительно много.Каков наилучший способ сделать это?

Первый ключ - найти все, собрать в список и вернуть его длину. 

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 (кликабельный) предикат и пытаюсь его использовать. 

?- 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) Как я могу объявить предикат, чтобы получить правильный ответ?

Ответы [ 4 ]

10 голосов
/ 09 мая 2011

Используйте экзистенциально количественную переменную, как если бы вы использовали setof: 

?- aggregate(count, X^permutation([1,2,3,4], X), N).
N = 24.
4 голосов
/ 27 сентября 2011

В SWI-Prolog есть гораздо более эффективная версия, которая также позволяет избежать блокировки глобального хранилища. Поэтому, просто используя nb_setval и nb_getval, вы увеличиваете производительность как минимум в 3 раза (подробнее о многопоточности). Совсем недавно другой вопрос был о подсчете решений. Будучи основой агрегации, это очевидная точка остановки при изучении Пролога. Чтобы оценить прирост эффективности, мы используем эти семантически эквивалентные вызовы: 

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.
3 голосов
/ 09 мая 2011

Существует также 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.
1 голос
/ 11 июня 2019

Это дополнение к сообщению Kaarels. В то же время некоторые системы прологов обновили свою реализацию агрегатов / 3 и aggregate_all / 3 Так что больше нет ошибки «Out of global stack»:

В SWI-прологе: 

Welcome to SWI-Prolog (threaded, 64 bits, version 8.1.6)

?- N is 10^8, aggregate_all(count, between(1, N, _), Total).
N = Total, Total = 100000000.

В Прологе в Екеке: 

Jekejeke Prolog 3, Runtime Library 1.3.7 (May 23, 2019)

?- use_module(library(advanced/arith)).
% 1 consults and 0 unloads in 16 ms.
Yes

?- use_module(library(advanced/aggregate)).
% 3 consults and 0 unloads in 94 ms.
Yes

?- N is 10^8, aggregate_all(count, between(1, N, _), Total).
N = 100000000,
Total = 100000000

Новые реализации сначала не вычисляют список, а затем подсчитывают длина списка. Скорее они используют какую-то глобальную переменную в качестве счетчика. Этот подход также используется для сумм, макс и т. Д ...

...