[Patch] Improve Locator

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

[Patch] Improve Locator

Gerd Petermann
Hi,

attached patch for the performance branch improves the Locator.
a) It uses a kd-tree to implement the findNextPoint() method.
This may also be usable in other routines, did not look at this until now.

The implementation is based on the demo in wikepedia:
wikipedia

The method in MapPointFastFindMap is slower and sometimes the
kd-tree finds nearer places.

b) added memoization to LocatorConfig.getCountryISOCode()

locator_v1.patch

Gerd
Reply | Threaded
Open this post in threaded view
|

Re: [Patch] Improve Locator

WanMil
Hi Gerd,

I have commited a modified version of b). I don't use a separate HashMap
because the isoMap is already there.

I would also commit the other parts. Please modify the following things:
* The K-D-Tree class has a test in the main() method. Please move this
to a JUnit test
* Please remove the commented old code

Thanks
WanMil

> Hi,
>
> attached patch for the performance branch improves the Locator.
> a) It uses a kd-tree to implement the findNextPoint() method.
> This may also be usable in other routines, did not look at this until now.
>
> The implementation is based on the demo in wikepedia:
> http://en.wikipedia.org/wiki/K-d_tree wikipedia
>
> The method in MapPointFastFindMap is slower and sometimes the
> kd-tree finds nearer places.
>
> b) added memoization to LocatorConfig.getCountryISOCode()
>
> http://gis.19327.n5.nabble.com/file/n5531583/locator_v1.patch
> locator_v1.patch
>
> Gerd
>
> --
> View this message in context: http://gis.19327.n5.nabble.com/Patch-Improve-Locator-tp5531583p5531583.html
> Sent from the Mkgmap Development mailing list archive at Nabble.com.
> _______________________________________________
> mkgmap-dev mailing list
> [hidden email]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: [Patch] Improve Locator

Gerd Petermann
Hi WanMil,


> Date: Wed, 7 Mar 2012 20:10:42 +0100
> From: [hidden email]
> To: [hidden email]
> Subject: Re: [mkgmap-dev] [Patch] Improve Locator
>
> Hi Gerd,
>
> I have commited a modified version of b). I don't use a separate HashMap
> because the isoMap is already there.

okay, I did not want to touch the original map, but I agree that your version is better

>
> I would also commit the other parts. Please modify the following things:
> * The K-D-Tree class has a test in the main() method. Please move this
> to a JUnit test
> * Please remove the commented old code

done, see attached patch.

Gerd


>
> Thanks
> WanMil
>
> > Hi,
> >
> > attached patch for the performance branch improves the Locator.
> > a) It uses a kd-tree to implement the findNextPoint() method.
> > This may also be usable in other routines, did not look at this until now.
> >
> > The implementation is based on the demo in wikepedia:
> > http://en.wikipedia.org/wiki/K-d_tree wikipedia
> >
> > The method in MapPointFastFindMap is slower and sometimes the
> > kd-tree finds nearer places.
> >
> > b) added memoization to LocatorConfig.getCountryISOCode()
> >
> > http://gis.19327.n5.nabble.com/file/n5531583/locator_v1.patch
> > locator_v1.patch
> >
> > Gerd
> >
> > --
> > View this message in context: http://gis.19327.n5.nabble.com/Patch-Improve-Locator-tp5531583p5531583.html
> > Sent from the Mkgmap Development mailing list archive at Nabble.com.
> > _______________________________________________
> > mkgmap-dev mailing list
> > [hidden email]
> > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>
> _______________________________________________
> mkgmap-dev mailing list
> [hidden email]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

locator_v2.patch (14K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [Patch] Improve Locator

WanMil
Thanks Gerd,

that looks great!

I have done some code simplifications (see attached version 3 of the
patch).
Example:
Locator: The construct Map<String, ArrayList<MapPoint>> is already
implemented as class MultiHashMap<String, MapPoint>.
K-D-Tree: Some code duplications could be saved by adding a simple
compare method isSmaller(..). (The test case was *very* useful to check
the correctness of the modifications).

Can you perform a short check on it?
Thanks!
WanMil

> Hi WanMil,
>
>
>  > Date: Wed, 7 Mar 2012 20:10:42 +0100
>  > From: [hidden email]
>  > To: [hidden email]
>  > Subject: Re: [mkgmap-dev] [Patch] Improve Locator
>  >
>  > Hi Gerd,
>  >
>  > I have commited a modified version of b). I don't use a separate HashMap
>  > because the isoMap is already there.
>
> okay, I did not want to touch the original map, but I agree that your
> version is better
>
>  >
>  > I would also commit the other parts. Please modify the following things:
>  > * The K-D-Tree class has a test in the main() method. Please move this
>  > to a JUnit test
>  > * Please remove the commented old code
>
> done, see attached patch.
>
> Gerd
>
>
>  >
>  > Thanks
>  > WanMil
>  >
>  > > Hi,
>  > >
>  > > attached patch for the performance branch improves the Locator.
>  > > a) It uses a kd-tree to implement the findNextPoint() method.
>  > > This may also be usable in other routines, did not look at this
> until now.
>  > >
>  > > The implementation is based on the demo in wikepedia:
>  > > http://en.wikipedia.org/wiki/K-d_tree wikipedia
>  > >
>  > > The method in MapPointFastFindMap is slower and sometimes the
>  > > kd-tree finds nearer places.
>  > >
>  > > b) added memoization to LocatorConfig.getCountryISOCode()
>  > >
>  > > http://gis.19327.n5.nabble.com/file/n5531583/locator_v1.patch
>  > > locator_v1.patch
>  > >
>  > > Gerd
>  > >
>  > > --
>  > > View this message in context:
> http://gis.19327.n5.nabble.com/Patch-Improve-Locator-tp5531583p5531583.html
>  > > Sent from the Mkgmap Development mailing list archive at Nabble.com.
>  > > _______________________________________________
>  > > mkgmap-dev mailing list
>  > > [hidden email]
>  > > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>  >
>  > _______________________________________________
>  > mkgmap-dev mailing list
>  > [hidden email]
>  > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>
>
> _______________________________________________
> mkgmap-dev mailing list
> [hidden email]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

locator_v3.patch (16K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: [Patch] Improve Locator

Gerd Petermann
Hi WanMil,

thanks, I did not try your modifications, I've just looked at the patch. All your changes look reasonable
to me.

Gerd

WanMil wrote
Thanks Gerd,

that looks great!

I have done some code simplifications (see attached version 3 of the
patch).
Example:
Locator: The construct Map<String, ArrayList<MapPoint>> is already
implemented as class MultiHashMap<String, MapPoint>.
K-D-Tree: Some code duplications could be saved by adding a simple
compare method isSmaller(..). (The test case was *very* useful to check
the correctness of the modifications).

Can you perform a short check on it?
Thanks!
WanMil

> Hi WanMil,
>
>
>  > Date: Wed, 7 Mar 2012 20:10:42 +0100
>  > From: [hidden email]
>  > To: [hidden email]
>  > Subject: Re: [mkgmap-dev] [Patch] Improve Locator
>  >
>  > Hi Gerd,
>  >
>  > I have commited a modified version of b). I don't use a separate HashMap
>  > because the isoMap is already there.
>
> okay, I did not want to touch the original map, but I agree that your
> version is better
>
>  >
>  > I would also commit the other parts. Please modify the following things:
>  > * The K-D-Tree class has a test in the main() method. Please move this
>  > to a JUnit test
>  > * Please remove the commented old code
>
> done, see attached patch.
>
> Gerd
>
>
>  >
>  > Thanks
>  > WanMil
>  >
>  > > Hi,
>  > >
>  > > attached patch for the performance branch improves the Locator.
>  > > a) It uses a kd-tree to implement the findNextPoint() method.
>  > > This may also be usable in other routines, did not look at this
> until now.
>  > >
>  > > The implementation is based on the demo in wikepedia:
>  > > http://en.wikipedia.org/wiki/K-d_tree wikipedia
>  > >
>  > > The method in MapPointFastFindMap is slower and sometimes the
>  > > kd-tree finds nearer places.
>  > >
>  > > b) added memoization to LocatorConfig.getCountryISOCode()
>  > >
>  > > http://gis.19327.n5.nabble.com/file/n5531583/locator_v1.patch
>  > > locator_v1.patch
>  > >
>  > > Gerd
>  > >
>  > > --
>  > > View this message in context:
> http://gis.19327.n5.nabble.com/Patch-Improve-Locator-tp5531583p5531583.html
>  > > Sent from the Mkgmap Development mailing list archive at Nabble.com.
>  > > _______________________________________________
>  > > mkgmap-dev mailing list
>  > > [hidden email]
>  > > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>  >
>  > _______________________________________________
>  > mkgmap-dev mailing list
>  > [hidden email]
>  > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>
>
> _______________________________________________
> mkgmap-dev mailing list
> [hidden email]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev


_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: [Patch] Improve Locator

Gerd Petermann
Hi WanMil,

there is one significant difference in MultiHashMap: it returns an emty list and not null when a key is not
found.
This can cause NPE in Locator, e.g. for data from Burkna Faso (see below)
The attached patch fixes this.

Locator_npe.patch

Gerd

java.lang.NullPointerException
        at uk.me.parabola.mkgmap.build.Locator.findCityByIsIn(Locator.java:333)
        at uk.me.parabola.mkgmap.build.Locator.autofillCities(Locator.java:363)
        at uk.me.parabola.mkgmap.build.MapBuilder.processCities(MapBuilder.java:267)
        at uk.me.parabola.mkgmap.build.MapBuilder.makeMap(MapBuilder.java:187)
        at uk.me.parabola.mkgmap.main.MapMaker.makeMap(MapMaker.java:97)
        at uk.me.parabola.mkgmap.main.MapMaker.makeMap(MapMaker.java:61)
        at uk.me.parabola.mkgmap.main.Main$1.call(Main.java:210)
        at uk.me.parabola.mkgmap.main.Main$1.call(Main.java:207)
        at java.util.concurrent.FutureTask$Sync.innerRun(FutureTask.java:303)
        at java.util.concurrent.FutureTask.run(FutureTask.java:138)
        at java.util.concurrent.ThreadPoolExecutor$Worker.runTask(ThreadPoolExecutor.java:886)
        at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:908)
        at java.lang.Thread.run(Thread.java:662)



GerdP wrote
Hi WanMil,

thanks, I did not try your modifications, I've just looked at the patch. All your changes look reasonable
to me.

Gerd

WanMil wrote
Thanks Gerd,

that looks great!

I have done some code simplifications (see attached version 3 of the
patch).
Example:
Locator: The construct Map<String, ArrayList<MapPoint>> is already
implemented as class MultiHashMap<String, MapPoint>.
K-D-Tree: Some code duplications could be saved by adding a simple
compare method isSmaller(..). (The test case was *very* useful to check
the correctness of the modifications).

Can you perform a short check on it?
Thanks!
WanMil

> Hi WanMil,
>
>
>  > Date: Wed, 7 Mar 2012 20:10:42 +0100
>  > From: [hidden email]
>  > To: [hidden email]
>  > Subject: Re: [mkgmap-dev] [Patch] Improve Locator
>  >
>  > Hi Gerd,
>  >
>  > I have commited a modified version of b). I don't use a separate HashMap
>  > because the isoMap is already there.
>
> okay, I did not want to touch the original map, but I agree that your
> version is better
>
>  >
>  > I would also commit the other parts. Please modify the following things:
>  > * The K-D-Tree class has a test in the main() method. Please move this
>  > to a JUnit test
>  > * Please remove the commented old code
>
> done, see attached patch.
>
> Gerd
>
>
>  >
>  > Thanks
>  > WanMil
>  >
>  > > Hi,
>  > >
>  > > attached patch for the performance branch improves the Locator.
>  > > a) It uses a kd-tree to implement the findNextPoint() method.
>  > > This may also be usable in other routines, did not look at this
> until now.
>  > >
>  > > The implementation is based on the demo in wikepedia:
>  > > http://en.wikipedia.org/wiki/K-d_tree wikipedia
>  > >
>  > > The method in MapPointFastFindMap is slower and sometimes the
>  > > kd-tree finds nearer places.
>  > >
>  > > b) added memoization to LocatorConfig.getCountryISOCode()
>  > >
>  > > http://gis.19327.n5.nabble.com/file/n5531583/locator_v1.patch
>  > > locator_v1.patch
>  > >
>  > > Gerd
>  > >
>  > > --
>  > > View this message in context:
> http://gis.19327.n5.nabble.com/Patch-Improve-Locator-tp5531583p5531583.html
>  > > Sent from the Mkgmap Development mailing list archive at Nabble.com.
>  > > _______________________________________________
>  > > mkgmap-dev mailing list
>  > > [hidden email]
>  > > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>  >
>  > _______________________________________________
>  > mkgmap-dev mailing list
>  > [hidden email]
>  > http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>
>
> _______________________________________________
> mkgmap-dev mailing list
> [hidden email]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev


_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
Reply | Threaded
Open this post in threaded view
|

Re: [Patch] Improve Locator

WanMil
Uups, thanks. Just commited it...

WanMil

> Hi WanMil,
>
> there is one significant difference in MultiHashMap: it returns an emty list
> and not null when a key is not
> found.
> This can cause NPE in Locator, e.g. for data from Burkna Faso (see below)
> The attached patch fixes this.
>
> http://gis.19327.n5.nabble.com/file/n5549780/Locator_npe.patch
> Locator_npe.patch
>
> Gerd
>
> java.lang.NullPointerException
>          at
> uk.me.parabola.mkgmap.build.Locator.findCityByIsIn(Locator.java:333)
>          at
> uk.me.parabola.mkgmap.build.Locator.autofillCities(Locator.java:363)
>          at
> uk.me.parabola.mkgmap.build.MapBuilder.processCities(MapBuilder.java:267)
>          at
> uk.me.parabola.mkgmap.build.MapBuilder.makeMap(MapBuilder.java:187)
>          at uk.me.parabola.mkgmap.main.MapMaker.makeMap(MapMaker.java:97)
>          at uk.me.parabola.mkgmap.main.MapMaker.makeMap(MapMaker.java:61)
>          at uk.me.parabola.mkgmap.main.Main$1.call(Main.java:210)
>          at uk.me.parabola.mkgmap.main.Main$1.call(Main.java:207)
>          at
> java.util.concurrent.FutureTask$Sync.innerRun(FutureTask.java:303)
>          at java.util.concurrent.FutureTask.run(FutureTask.java:138)
>          at
> java.util.concurrent.ThreadPoolExecutor$Worker.runTask(ThreadPoolExecutor.java:886)
>          at
> java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:908)
>          at java.lang.Thread.run(Thread.java:662)
>
>
>
>
> GerdP wrote
>>
>> Hi WanMil,
>>
>> thanks, I did not try your modifications, I've just looked at the patch.
>> All your changes look reasonable
>> to me.
>>
>> Gerd
>>
>>
>> WanMil wrote
>>>
>>> Thanks Gerd,
>>>
>>> that looks great!
>>>
>>> I have done some code simplifications (see attached version 3 of the
>>> patch).
>>> Example:
>>> Locator: The construct Map&lt;String, ArrayList&lt;MapPoint&gt;>  is
>>> already
>>> implemented as class MultiHashMap&lt;String, MapPoint&gt;.
>>> K-D-Tree: Some code duplications could be saved by adding a simple
>>> compare method isSmaller(..). (The test case was *very* useful to check
>>> the correctness of the modifications).
>>>
>>> Can you perform a short check on it?
>>> Thanks!
>>> WanMil
>>>
>>>> Hi WanMil,
>>>>
>>>>
>>>>   >  Date: Wed, 7 Mar 2012 20:10:42 +0100
>>>>   >  From: wmgcnfg@
>>>>   >  To: mkgmap-dev@.org
>>>>   >  Subject: Re: [mkgmap-dev] [Patch] Improve Locator
>>>>   >
>>>>   >  Hi Gerd,
>>>>   >
>>>>   >  I have commited a modified version of b). I don't use a separate
>>>> HashMap
>>>>   >  because the isoMap is already there.
>>>>
>>>> okay, I did not want to touch the original map, but I agree that your
>>>> version is better
>>>>
>>>>   >
>>>>   >  I would also commit the other parts. Please modify the following
>>>> things:
>>>>   >  * The K-D-Tree class has a test in the main() method. Please move
>>>> this
>>>>   >  to a JUnit test
>>>>   >  * Please remove the commented old code
>>>>
>>>> done, see attached patch.
>>>>
>>>> Gerd
>>>>
>>>>
>>>>   >
>>>>   >  Thanks
>>>>   >  WanMil
>>>>   >
>>>>   >  >  Hi,
>>>>   >  >
>>>>   >  >  attached patch for the performance branch improves the Locator.
>>>>   >  >  a) It uses a kd-tree to implement the findNextPoint() method.
>>>>   >  >  This may also be usable in other routines, did not look at this
>>>> until now.
>>>>   >  >
>>>>   >  >  The implementation is based on the demo in wikepedia:
>>>>   >  >  http://en.wikipedia.org/wiki/K-d_tree wikipedia
>>>>   >  >
>>>>   >  >  The method in MapPointFastFindMap is slower and sometimes the
>>>>   >  >  kd-tree finds nearer places.
>>>>   >  >
>>>>   >  >  b) added memoization to LocatorConfig.getCountryISOCode()
>>>>   >  >
>>>>   >  >  http://gis.19327.n5.nabble.com/file/n5531583/locator_v1.patch
>>>>   >  >  locator_v1.patch
>>>>   >  >
>>>>   >  >  Gerd
>>>>   >  >
>>>>   >  >  --
>>>>   >  >  View this message in context:
>>>> http://gis.19327.n5.nabble.com/Patch-Improve-Locator-tp5531583p5531583.html
>>>>   >  >  Sent from the Mkgmap Development mailing list archive at
>>>> Nabble.com.
>>>>   >  >  _______________________________________________
>>>>   >  >  mkgmap-dev mailing list
>>>>   >  >  mkgmap-dev@.org
>>>>   >  >  http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>>>>   >
>>>>   >  _______________________________________________
>>>>   >  mkgmap-dev mailing list
>>>>   >  mkgmap-dev@.org
>>>>   >  http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>>>>
>>>>
>>>> _______________________________________________
>>>> mkgmap-dev mailing list
>>>> mkgmap-dev@.org
>>>> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>>>
>>>
>>> _______________________________________________
>>> mkgmap-dev mailing list
>>> mkgmap-dev@.org
>>> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev
>>>
>>
>
>
> --
> View this message in context: http://gis.19327.n5.nabble.com/Patch-Improve-Locator-tp5531583p5549780.html
> Sent from the Mkgmap Development mailing list archive at Nabble.com.
> _______________________________________________
> mkgmap-dev mailing list
> [hidden email]
> http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev

_______________________________________________
mkgmap-dev mailing list
[hidden email]
http://www.mkgmap.org.uk/mailman/listinfo/mkgmap-dev