agrégat/3 en swi-prolog

Question

Je dois compter tous X, que some_predicate(X) et il ya vraiment beaucoup de tels X. Quelle est la meilleure façon de faire cela? Le premier indice est de tout trouver, de l'accumuler dans une liste et de lui restituer la longueur.

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

(permutation/2 est exemple seulement montrant qu'il existe de nombreuses variantes et il est mauvaise façon de recueillir tous)

De toute évidence, je pile débordement.

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

Than, je suis en train de remplacer findall à setof et rien ne change.

Enfin, j'ai fondé aggregate (cliquable) prédicats et en essayant de l'utiliser.

?- 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 ; 

Tout est faux, je pense. Je préfère obtenir quelque chose comme

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

1) Qu'est-ce que je fais mal?

2) Comment puis-je déclarer le prédicat pour obtenir la bonne réponse?

Answer 1

Utilisez une variable existentiellement quantifié, comme vous le feriez avec setof:

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

Answer 2

Il est également aggregate_all/3:

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

Cependant, dans la mesure où les dépassements d'exécution et de la pile sont concernés, il semble effectuer tout aussi bien à votre findall + length solution:

?- 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 

Vous pouvez compter les solutions en utilisant assert/retract, cela est assez lent, mais on éviter le problème « hors de la pile »:

?- 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. 

Answer 3

Dans SWI-Prolog il existe une version beaucoup plus efficace, qui évitent aussi verrouiller le magasin global. Donc en utilisant simplement nb_setval et nb_getval, vous gagnez au moins 3 fois les performances (plus sur le multithreading). Il y a peu de temps, une autre question portait sur le comptage des solutions. Être la base de l'agrégation c'est un point d'arrêt évident tout en apprenant Prolog. Pour évaluer le gain d'efficacité, nous obtenons l'utilisation de ces appels monofil sémantiquement équivalents:

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). 

Sur mon système, je reçois

?- [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.