Блог

Мне нужно подсчитать все, 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] (доступно для просмотра) и пытаюсь использовать 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

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

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

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

 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.
  

Существует также 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.
  

Это дополнение к сообщению Каарела. Тем временем некоторые системы Prolog обновили свою реализацию aggregate/3 и aggregate_all/3 . Таким образом, ошибки «Вне глобального стека» больше нет:

В SWI-Prolog:

 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.
  

In Jekejeke Prolog:

 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
  

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