Bug #100677 for Map-Tube: Better performance?

Tue Dec 02 17:08:25 2014 SREZIC [...] cpan.org - Ticket created

Subject:

Better performance?

I think the get_shortest_route() performance can be greatly improved by using an alternative route search algorithm, e.g. A*.

Tue Dec 02 17:58:45 2014 SREZIC [...] cpan.org - Correspondence added

On 2014-12-02 17:08:25, SREZIC wrote: Show quoted text

> I think the get_shortest_route() performance can be greatly improved > by using an alternative route search algorithm, e.g. A*.

It looks like there's a performance regression between Map::Tube 2.26 and 2.27. With 2.26: $ time perl5.12.5 -MMap::Tube::London -E '$t = Map::Tube::London->new; say $t->get_shortest_route("Aldgate","Bayswater")' Aldgate, Liverpool Street, Bank, Waterloo, Westminster, Green Park, Bond Street, Marble Arch, Lancaster Gate, Queensway, Notting Hill Gate, Bayswater perl5.12.5 -MMap::Tube::London -E 0.10s user 0.03s system 81% cpu 0.152 total With 2.27: $ time perl5.12.5 -MMap::Tube::London -E '$t = Map::Tube::London->new; say $t->get_shortest_route("Aldgate","Bayswater")' Aldgate (Circle,Metropolitan), Liverpool Street (Central,Circle,Hammersmith & City,Metropolitan), Bank (Central,Northern,Waterloo & City), Waterloo (Northern,Bakerloo,Jubilee,Waterloo & City), Westminster (Circle,District,Jubilee), Green Park (Victoria,Jubilee,Piccadilly), Bond Street (Central,Jubilee), Marble Arch (Central), Lancaster Gate (Central), Queensway (Central), Notting Hill Gate (Central,Circle,District), Bayswater (Circle,District) perl5.12.5 -MMap::Tube::London -E 47.78s user 0.03s system 99% cpu 47.818 total

Wed Dec 03 10:11:41 2014 MANWAR [...] cpan.org - Correspondence added

Hi, Thanks for raising the issue and a very valid one. I have made progress in the at direction and pushed the code v2.30. Below is my result of post fix: manwar@ubuntu:~/$ time perl -MMap::Tube::London -E 'print "Map::Tube v$Map::Tube::VERSION\n\n"; $t = Map::Tube::London->new; say $t->get_shortest_route("Aldgate","Bayswater")' Map::Tube v2.30 Aldgate (Circle,Metropolitan), Liverpool Street (Central,Circle,Hammersmith & City,Metropolitan), Bank (Central,Northern,Waterloo & City), Waterloo (Northern,Bakerloo,Jubilee,Waterloo & City), Westminster (Circle,District,Jubilee), Green Park (Victoria,Jubilee,Piccadilly), Bond Street (Central,Jubilee), Marble Arch (Central), Lancaster Gate (Central), Queensway (Central), Notting Hill Gate (Central,Circle,District), Bayswater (Circle,District) real 0m0.183s user 0m0.172s sys 0m0.008s manwar@ubuntu:~/$ time perl -MMap::Tube::London -E 'print "Map::Tube v$Map::Tube::VERSION\n\n"; $t = Map::Tube::London->new; say $t->get_shortest_route("Aldgate","Bayswater")' Map::Tube v2.26 Aldgate, Liverpool Street, Bank, Waterloo, Westminster, Green Park, Bond Street, Marble Arch, Lancaster Gate, Queensway, Notting Hill Gate, Bayswater real 0m0.175s user 0m0.160s sys 0m0.016s Best Regards, Mohammad S Anwar

Wed Dec 03 10:11:41 2014 The RT System itself - Status changed from 'new' to 'open'

Wed Dec 03 13:52:33 2014 SREZIC [...] cpan.org - Correspondence added

On 2014-12-03 10:11:41, MANWAR wrote: Show quoted text

> Hi, > > Thanks for raising the issue and a very valid one. I have made > progress in the at direction and pushed the code v2.30. Below is my > result of post fix: > > manwar@ubuntu:~/$ time perl -MMap::Tube::London -E 'print "Map::Tube > v$Map::Tube::VERSION\n\n"; $t = Map::Tube::London->new; say $t-

> >get_shortest_route("Aldgate","Bayswater")'

> Map::Tube v2.30 > > Aldgate (Circle,Metropolitan), Liverpool Street > (Central,Circle,Hammersmith & City,Metropolitan), Bank > (Central,Northern,Waterloo & City), Waterloo > (Northern,Bakerloo,Jubilee,Waterloo & City), Westminster > (Circle,District,Jubilee), Green Park (Victoria,Jubilee,Piccadilly), > Bond Street (Central,Jubilee), Marble Arch (Central), Lancaster Gate > (Central), Queensway (Central), Notting Hill Gate > (Central,Circle,District), Bayswater (Circle,District) > > real 0m0.183s > user 0m0.172s > sys 0m0.008s > > manwar@ubuntu:~/$ time perl -MMap::Tube::London -E 'print "Map::Tube > v$Map::Tube::VERSION\n\n"; $t = Map::Tube::London->new; say $t-

> >get_shortest_route("Aldgate","Bayswater")'

> Map::Tube v2.26 > > Aldgate, Liverpool Street, Bank, Waterloo, Westminster, Green Park, > Bond Street, Marble Arch, Lancaster Gate, Queensway, Notting Hill > Gate, Bayswater > > real 0m0.175s > user 0m0.160s > sys 0m0.016s > > Best Regards, > > Mohammad S Anwar

Thanks, performance is acceptable now. Regards, Slaven

Wed Dec 03 13:52:33 2014 SREZIC [...] cpan.org - Status changed from 'open' to 'resolved'

Wed Dec 03 13:52:34 2014 SREZIC [...] cpan.org - Fixed in 2.30 added