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] （可点击的）谓词系列，并尝试使用aggregate/3and 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 回答
3

这是 Kaarel 帖子的附录。同时，一些 Prolog 系统已经更新了它们的实现aggregate/3和aggregate_all/3. 所以不再有“Out of global stack”错误：

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

在 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等...

于 2019-06-10T22:18:26.947 回答