markb@sdcrdcf.UUCP (06/08/84)
Does any one have a faster list reverse routine then:
reverse([H|T],Y) :-
rev1(H,[],T,Y).
reverse([],[]).
rev1(X,L,[],[X|L]).
rev1(X,L,[H|T],Y) :-
rev1(H,[X|L],T,Y).
This appears to be O(n): n length of list.
The "usual" definition of reverse:
reverse([],[]).
reverse([H|T],X) :-
reverse(T,T1),
append(T1,H,X).
is O(n**2) at least.
Mark Biggar
{allegra,burdvax,cbosgd,hplabs,ihnp4,sdcsvax}!sdcrdcf!markbdep@allegra.UUCP (Dewayne E. Perry) (06/14/84)
chomp :- bite, chomp.
Mark Biggar asked if anyone had a faster list reverse than:
reverse([H|T],Y) :- rev1(H,[],T,Y).
reverse([],[]).
rev1(X,L,[],[X|L]).
rev1(X,L,[H|T],Y) :- rev1(H,[X|L],T,Y).
Wellll, faster is possible in several different ways - all of which
exploit the implementation of prolog, but which have very little
to do with logic programming (or with improving the complexity of O(n)).
1. The following version is probably faster since there is one less
parameter in the procedure (though probably not significantly
faster).
reverse(X,Y) :- rev1([],X,Y).
reverse([],[]).
rev1(L,[H|[]],[H|L]).
rev1(L,[H|T],Y) :- rev1([H|L],T,Y).
2. The following implementation exploits the order in which rules
are tried and provides significant improvements in execution.
In general, position the terminating conditions after the normal
conditions in a prolog procedure.
reverse(X,Y) :- rev1([],X,Y).
reverse([],[]).
rev1(L,[H|T],Y) :- rev1([H|L],T,Y).
rev1(L,[H|[]],[H|L]).
The variant prescription is to give the most used rules first
and the less used rules following.
3. Faster yet is the implementation that takes two elements at a
time and reverses them.
reverse(X,Y) :- rev1([],X,Y).
reverse([],[]).
rev1(L,[H1,H2|T],Y) :- rev1([H2,H1|L],T,Y).
rev1(L,[H|[]],[H|L]).
rev1(L,[H1,H2|[]], [H2,H1|L]).
And of course, taking four elements at a time, etc...
4. In larger procedures (ie, ones with more rules), the judicious use
of the cut may have extremely beneficial effects on the efficiency
of your implementations. The trick is finding where to put them.
Prolog implementation recipe for efficient prolog programs:
1. Start with prolog normal form algorithms (which generaly are straight-
forward, easy to understand, and burdened with terrible orders of
complexity - n factorial, 2**n, etc).
2. Then think hard to find a better algorithm with more reasonable
complexity characteristics. Watch out here! Some of the improvements
that you think should speedup the average case may cause worse
execution behaviour because of the underlying prolog implementation.
(This is one of the problems of having such a complex underlying
implementation.)
3. Then apply the above hacks to wring out a few more cycles.
happy_hacking :- hack, happy_hacking.