Some strange result

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|

Some strange result

Sylvain Julmy
Hi,

at first, excuse me for my English, I'm not very good at...

At the School of Engineering and Architecture of Fribourg, Switzerland,
we have a Prolog course in the thirs year of the Bachelor cursus. In an
exercice, we need to study a programm wo resolve the Hanoi tower problem.

I have create a simple predicat that's simply execute the solve1
predicat (see attachment : hanoi.pl) and the time computation is
increasing and we dont know why.

That's the output when i run my test_solve1 predicat :

| ?- test_solve1(25,10).
 25: nbrMoves = 1023.0   6ms
 24: nbrMoves = 1023.0   9ms
 23: nbrMoves = 1023.0   15ms
 22: nbrMoves = 1023.0   18ms
 21: nbrMoves = 1023.0   22ms
 20: nbrMoves = 1023.0   23ms
 19: nbrMoves = 1023.0   25ms
 18: nbrMoves = 1023.0   25ms
 17: nbrMoves = 1023.0   26ms
 16: nbrMoves = 1023.0   27ms
 15: nbrMoves = 1023.0   31ms
 14: nbrMoves = 1023.0   34ms
 13: nbrMoves = 1023.0   168ms
 12: nbrMoves = 1023.0   204ms
 11: nbrMoves = 1023.0   223ms
 10: nbrMoves = 1023.0   251ms
 9: nbrMoves = 1023.0   270ms
 8: nbrMoves = 1023.0   291ms
 7: nbrMoves = 1023.0   313ms
 6: nbrMoves = 1023.0   334ms
 5: nbrMoves = 1023.0   357ms
 4: nbrMoves = 1023.0   381ms
 3: nbrMoves = 1023.0   399ms
 2: nbrMoves = 1023.0   419ms
 1: nbrMoves = 1023.0   441ms


I hope someone could find a good response to this !

Dear,
Sylvain Julmy
School of Engineering and Architecture of Fribourg
Switzerland

_______________________________________________
Users-prolog mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/users-prolog

hanoi.pl (970 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: Some strange result

Daniel Diaz-3
Hi

This is due to heavy use of assert followed by retract on the currently used predicate hanoiDyn/5.
A solution consists in using another predicate for tabling.

:- dynamic(tabled/5).

hanoiDyn(1,_A,_B,_,1).                      %--- move _A to _B

hanoiDyn(N,A,B,C,Moves) :-
    tabled(N, A,B,C,Moves), !. % tabled: return the #moves

hanoiDyn(N,A,B,C,Moves) :-
            N>1,
            N1 is N-1,
            hanoiDyn(N1,A,C,B,Moves1),        %--- move N-1 discs
            asserta(tabled(N1,A,C,B,Moves1)),

            hanoiDyn(N1,C,B,A,Moves2),        %--- move N-1 discs

            retract(tabled(N1,A,C,B,_)),

            Moves is Moves1 + Moves2 + 1.

Remark that, when retract is called, only one clause for tabled/5 is present in the database. You could then use retractall which is faster. Replace retract(tabled(N1,A,C,B,_)), by

            retractall(tabled(_,_,_,_,_)),

This should be even faster.

Ramrk also that you can further speed up removing A,B,C from tabled data (moving N disks always require the same number of move independently from A,B,C). You thus have a tabled/2 predicate : tabled(N,Moves).

Finally, you could keep your tabled data until the end of the predicate and do the retractall only in the solve1/2 predicate. But this depends on what you try to measure.

Daniel

Le 13/11/2014 18:37, Sylvain Julmy a écrit :
Hi,

at first, excuse me for my English, I'm not very good at...

At the School of Engineering and Architecture of Fribourg, Switzerland,
we have a Prolog course in the thirs year of the Bachelor cursus. In an
exercice, we need to study a programm wo resolve the Hanoi tower problem.

I have create a simple predicat that's simply execute the solve1
predicat (see attachment : hanoi.pl) and the time computation is
increasing and we dont know why.

That's the output when i run my test_solve1 predicat :

| ?- test_solve1(25,10).
 25: nbrMoves = 1023.0   6ms
 24: nbrMoves = 1023.0   9ms
 23: nbrMoves = 1023.0   15ms
 22: nbrMoves = 1023.0   18ms
 21: nbrMoves = 1023.0   22ms
 20: nbrMoves = 1023.0   23ms
 19: nbrMoves = 1023.0   25ms
 18: nbrMoves = 1023.0   25ms
 17: nbrMoves = 1023.0   26ms
 16: nbrMoves = 1023.0   27ms
 15: nbrMoves = 1023.0   31ms
 14: nbrMoves = 1023.0   34ms
 13: nbrMoves = 1023.0   168ms
 12: nbrMoves = 1023.0   204ms
 11: nbrMoves = 1023.0   223ms
 10: nbrMoves = 1023.0   251ms
 9: nbrMoves = 1023.0   270ms
 8: nbrMoves = 1023.0   291ms
 7: nbrMoves = 1023.0   313ms
 6: nbrMoves = 1023.0   334ms
 5: nbrMoves = 1023.0   357ms
 4: nbrMoves = 1023.0   381ms
 3: nbrMoves = 1023.0   399ms
 2: nbrMoves = 1023.0   419ms
 1: nbrMoves = 1023.0   441ms


I hope someone could find a good response to this !

Dear,
Sylvain Julmy
School of Engineering and Architecture of Fribourg
Switzerland



_______________________________________________
Users-prolog mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/users-prolog


--
Ce message a été vérifié par MailScanner pour des virus ou des polluriels et rien de suspect n'a été trouvé.
_______________________________________________
Users-prolog mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/users-prolog