tree@sun.soe.clarkson.edu (Tom Emerson) (03/20/89)
I am looking for the Prolog source for the naive reverse benchmark. Thanks in advance for your help. Tom +----------------------------------------------------------------------+ | It matters not how strait the gate, | | | How charged with punishments the scroll, | | | I am the master of my fate; |Tom Emerson | | I am the captain of my soul. |tree@sun.soe.clarkson.edu | | --- From W.E. Henley, "Invictus" | | +----------------------------------------------------------------------+
broome@adm.BRL.MIL (Paul Broome ) (03/20/89)
In <2695@sun.soe.clarkson.edu> tree@sun.soe.clarkson.edu (Tom Emerson) writes:
:I am looking for the Prolog source for the naive reverse benchmark.
The naive reverse benchmark is popular because it generates a lot of procedure
calls. But it seems that benchmarks for NP-complete problems would be
most interesting since they require search and search is easy in Prolog. Plus
we'd be attacking a famous unsolved problem.
I know about the 'Stock-cutting problem' by Dincbas, et al in LP'88. Has
anyone heard of other benchmarks for NP-complete problems?
Paul <Broome@brl.mil>
p.s. The following is bench/nrev.P from the SBProlog distribution.
-----------------
/* The naive reverse benchmark */
nrev([],[]).
nrev([X|Rest],Ans) :- nrev(Rest,L), append(L,[X],Ans).
append([],L,L).
append([X|L1],L2,[X|L3]) :-
append(L1,L2,L3).
bench(Count) :- cputime(T0),dodummy(Count),cputime(T1),
dobench(Count),cputime(T2),
report(Count,T0,T1,T2).
dobench(Count) :- data(List),repeat(Count),nrev(List,_),fail.
dobench(_).
dodummy(Count) :- data(List),repeat(Count),dummy(List,_),fail.
dodummy(_).
dummy(_,_).
data(X) :- data(X,30).
data([],0).
data([a|Y],N) :- N > 0, N1 is N-1, data(Y,N1).
/* data([a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,aa,bb,cc,dd]). */
repeat(N).
repeat(N) :- N > 1, N1 is N-1, repeat(N1).
report(Count,T0,T1,T2) :- write(T0),nl,write(T1),nl,write(T2),nl,
Time1 is T1 - T0,write(Time1),nl,
Time2 is T2 - T1,write(Time2),nl,
Time is Time2-Time1,write(Time),nl,
Lips is (496*Count*1000)/Time,
write('Lips = '),write(Lips), nl.