Make some Rules faster
Author Message
Make some Rules faster

Hi,

can you please tell me, how i could make this two rules faster ?

/* Cuts Count Elements off from a List and returns the rest
Usage: cutof(List,Count,Resultlist)
*/
cutof(List,0,List):- !.
Nr \== 0,
Nr2 is Nr - 1,
cutof(Tail,Nr2,Endlist).

/* Cuts X elements off from a list and return the list
of cutted elements in cuttedof(Listofcuttedelems).
Usage: cuttedof(List,0,_,[]),cuttedof(Listofcuttedelems)
*/

cuttedof(List,0,List,Cuttedof):-
retractall(cuttedof(_)),
reverse(Cuttedof,X),
assert(cuttedof(X)),
!.
Nr \== 0,Nr2 is Nr - 1,
cuttedof(Tail,Nr2,Endlist,Cuttedof2).

Any help would be appreciated.
Christoph

Sat, 22 May 2004 22:02:26 GMT
Make some Rules faster

Quote:
> Hi,

> can you please tell me, how i could make this two rules faster ?

> /* Cuts Count Elements off from a List and returns the rest
>  Usage: cutof(List,Count,Resultlist)
> */
> cutof(List,0,List):- !.
>  Nr \== 0,
>  Nr2 is Nr - 1,
>  cutof(Tail,Nr2,Endlist).

Not much can be done here, but you can lose the cut, the comparison, or both.
The difference is in what they do to get the answer and what they do when
backtracking occurs. You didn't specify how it should be 'faster'.

cutoff1(L,0,L).
cutoff1([_|T],N,L1):-
N>0,
N1 is N - 1,
cutoff1(T,N1,L1).

cutoff2(L,0,L):-!.
cutoff2([_|T],N,L):-
N1 is N - 1,
cutoff2(T,N1,L).

cutoff3(L,0,L).
cutoff3([_|T],N,L):-
N1 is N - 1,
cutoff3(T,N1,L).

Quote:
> /* Cuts X elements off from a list and return the list
> of cutted elements in cuttedof(Listofcuttedelems).
> Usage: cuttedof(List,0,_,[]),cuttedof(Listofcuttedelems)
> */

> cuttedof(List,0,List,Cuttedof):-
>  retractall(cuttedof(_)),
>  reverse(Cuttedof,X),
>  assert(cuttedof(X)),
>  !.
>  Nr \== 0,Nr2 is Nr - 1,
>  cuttedof(Tail,Nr2,Endlist,Cuttedof2).

Throw this away. Avoid !, assert, retract, reverse and append when possible.
This combination is particularly ugly because it is completely unnecessary.
HINT(make sure you understand how this works, try using trace(thing).):
----------------------------------
?- [user].
|    thing([],[]).
|    thing([H|T],[foo,H,bar|T1]):-thing(T,T1).
|
% user compiled 0.00 sec, 68 bytes
Yes
?- thing([1,2,3],X).
X = [foo, 1, bar, foo, 2, bar, foo, 3, bar] ;
No
?-
-----------------------------------
cuttedof(List,0,List,[]).
% writing the body is left as an exercise

--------------
Geoff

Sun, 23 May 2004 00:26:15 GMT
Make some Rules faster

Quote:

> /* Cuts Count Elements off from a List and returns the rest
>  Usage: cutof(List,Count,Resultlist)
> */
> cutof(List,0,List):- !.
>  Nr \== 0,
>  Nr2 is Nr - 1,
>  cutof(Tail,Nr2,Endlist).

Without having tested it, I think the following will be "faster":

cutof(In,N,Out) :-
(N =< 0 ->
Out = In
;
In = [_|NewIn],
NewN is N - 1,
cutof(NewIn,NewN,Out)
).

And indeed, throw away the code with the append/reverse; that's the best way to get a faster solution.

Cheers

Bart Demoen

Sun, 23 May 2004 00:46:18 GMT
Make some Rules faster

Quote:

> Hi,

> can you please tell me, how i could make this two rules faster ?

> /* Cuts Count Elements off from a List and returns the rest
>  Usage: cutof(List,Count,Resultlist)
> */
> cutof(List,0,List):- !.
>  Nr \== 0,
>  Nr2 is Nr - 1,
>  cutof(Tail,Nr2,Endlist).

If you know that you're never going to drop more than N elements (where
N is, say, 10) from a list, you can do something like this:

cutof(0,List,List).
cutof(1,[_|List],List).
cutof(2,[_,_|List],List).
cutof(3,[_,_,_|List],List).
...
cutof(10,[_,_,_,_,_,_,_,_,_|List],List).

Having the integer as the first argument is important for indexing
reasons. This is as fast as it can get.

You can also combine these clauses with clauses for the more general
case. If you want to drop a small number of elements from very many
lists, and a large number of elements from just a few lists, this may be
a good strategy.

-- Torbj?rn

--
----------------------------------------------------------------
Torbj?rn Lager                Lecturer in
Department of Linguistics     Computational Linguistics
Stockholm University          ==================================
Universitetsv?gen 10          Tel: +46 (0)8 163938
S-106 91 Stockholm            Fax: +46 (0)8 155389
Sweden                        WWW: http://www.ling.gu.se/~lager/
----------------------------------------------------------------

Sun, 23 May 2004 03:20:00 GMT
Make some Rules faster

Quote:

> If you know that you're never going to drop more than N elements (where
> N is, say, 10) from a list, you can do something like this:
>  cutof(0,List,List).
>  cutof(1,[_|List],List).
>  cutof(2,[_,_|List],List).
>  cutof(3,[_,_,_|List],List).
>    ...
>  cutof(10,[_,_,_,_,_,_,_,_,_|List],List).
> Having the integer as the first argument is important for indexing
> reasons. This is as fast as it can get.

Doesn't the unification of the goal

cutof(LargeNumber,ListTooBig,List)

have to recursively descend the list from head to tail?
This would mean n + (n-1) + (n-2) + ... + 1 matches, or
n^2/2, and perhaps worse if cutof/3 had some more interesting
work to do like unify complex terms or lists into each of the
elements of the list.  In other words, is there an upper limit
to how useful this approach is (purely from the perspective of
efficiency), and to what extent would this be Prolog-implementation
dependent?

Thx,

John Paolillo
SLIS and Informatics
Indiana University

Sun, 23 May 2004 02:48:59 GMT
Make some Rules faster

Quote:
>> cuttedof(List,0,List,Cuttedof):-
>> [...]
> Throw this away. Avoid !, assert, retract, reverse and append when possible.
> This combination is particularly ugly because it is completely unnecessary.
> HINT(make sure you understand how this works, try using trace(thing).):
> ----------------------------------
> ?- [user].
> |    thing([],[]).
> |    thing([H|T],[foo,H,bar|T1]):-thing(T,T1).

well, if i trace this i get:

[debug]  ?- thing([a,b,c],X).
T Call: (7) thing([a, b, c], _G378)
T Call: (8) thing([b, c], _G443)
T Call: (9) thing([c], _G452)
T Call: (10) thing([], _G461)
T Exit: (10) thing([], [])
T Exit: (9) thing([c], [foo, c, bar])
T Exit: (8) thing([b, c], [foo, b, bar, foo, c, bar])
T Exit: (7) thing([a, b, c], [foo, a, bar, foo, b, bar, foo, c|...])

X = [foo, a, bar, foo, b, bar, foo, c, bar]

what i don't understand are the exit's, i mean i got the rule to work
how it should, but i don't understand it.

cuttedof(List,0,List,[]).
Nr2 is Nr -1,
cuttedof(Tail,Nr2,Endoflist,Cuttedof).

the trace gives me:

[debug]  ?- cuttedof([a,b,c,d,e,f,g,h],3,X,Y).
T Call: (7) cuttedof([a, b, c, d, e, f, g, h], 3, _G496, _G497)
T Call: (8) cuttedof([b, c, d, e, f, g, h], 2, _G496, _G588)
T Call: (9) cuttedof([c, d, e, f, g, h], 1, _G496, _G594)
T Call: (10) cuttedof([d, e, f, g, h], 0, _G496, _G600)
T Exit: (10) cuttedof([d, e, f, g, h], 0, [d, e, f, g, h], [])
T Exit: (9) cuttedof([c, d, e, f, g, h], 1, [d, e, f, g, h], [c])
T Exit: (8) cuttedof([b, c, d, e, f, g, h], 2, [d, e, f, g, h], [b,
c])
T Exit: (7) cuttedof([a, b, c, d, e, f, g, h], 3, [d, e, f, g, h],
[a, b, c])

X = [d, e, f, g, h]
Y = [a, b, c]

how is it working, how does Prolog modify the vars when exiting, this
is what i don't understand.

Christoph

Sun, 23 May 2004 03:13:00 GMT
Make some Rules faster

<snip>

Quote:
> what i don't understand are the exit's, i mean i got the rule to work
> how it should, but i don't understand it.

RULE 1:
> cuttedof(List,0,List,[]).

RULE 2:

Quote:
>  Nr2 is Nr -1,
>  cuttedof(Tail,Nr2,Endoflist,Cuttedof).

> the trace gives me:

> [debug]  ?- cuttedof([a,b,c,d,e,f,g,h],3,X,Y).
>  T Call: (7) cuttedof([a, b, c, d, e, f, g, h], 3, _G496, _G497)

rule 1 doesn't apply, to prove rule 2 I have to unify the above with
cuttedof([a|[b,c,d,e,f,g,h]],3,_G496,[a|_G588])
do the subtraction and prove cuttedof([b,c,d,e,f,g,h],2,_G496 ,_G588)
What has happened is that _G497 has unified with [a|_G588] we just need
to find out what _G588 is unified with

Quote:
>  T Call: (8) cuttedof([b, c, d, e, f, g, h], 2, _G496, _G588)

Rule 2:_G588 unifies with [b|_G594] so _G497 is now unified with [a,b|_G594]

Quote:
>  T Call: (9) cuttedof([c, d, e, f, g, h], 1, _G496, _G594)

Rule 2:_G594 unifies with [c|_G600] so _G497 is now unified with [a,b,c|_G600]

Quote:
>  T Call: (10) cuttedof([d, e, f, g, h], 0, _G496, _G600)

Rule 1:_G600 unifies with [] so _G497 is now unified with [a,b,c]

Quote:
>  T Exit: (10) cuttedof([d, e, f, g, h], 0, [d, e, f, g, h], []) <-this is
_G600
>  T Exit: (9) cuttedof([c, d, e, f, g, h], 1, [d, e, f, g, h], [c]) <- _G594
>  T Exit: (8) cuttedof([b, c, d, e, f, g, h], 2, [d, e, f, g, h], [b,
> c]) <-_G588
>  T Exit: (7) cuttedof([a, b, c, d, e, f, g, h], 3, [d, e, f, g, h],
> [a, b, c]) <-_G497

Here's a sneaky way to show this happening:

?- [user].
|: cuttedof(List,0,List,[],Peek):-write(Peek),nl.
|:     write(Peek),nl,
|:     Nr2 is Nr -1,
|:     cuttedof(Tail,Nr2,Endoflist,Cuttedof,Peek),
|:     write(Peek),nl.
|:
% user compiled 0.00 sec, 252 bytes

Yes
?- cuttedof([1,2,3,4,5,6,7],3,X,Y,Y). % Y and Peek will be unified all the way
down
[1|_G455] <- Rule2a- first write
[1, 2|_G461] <- Rule2b- first write
[1, 2, 3|_G467] <- Rule2c- first write
[1, 2, 3] <-Rule1
[1, 2, 3] <- Rule2c- second write
[1, 2, 3] <- Rule2b- second write
[1, 2, 3] <- Rule2a- second write

X = [4, 5, 6, 7]
Y = [1, 2, 3] ;
[1, 2, 3, 4|_G473]
[1, 2, 3, 4, 5|_G479]
[1, 2, 3, 4, 5, 6|_G485]
[1, 2, 3, 4, 5, 6, 7|_G491]

No
?-

Hope this makes it clearer,
Geoff

Sun, 23 May 2004 05:35:48 GMT

 Page 1 of 1 [ 7 post ]

Relevant Pages