[mkgmap-dev] [PATCH v1] LocationHook speedup

Sat Dec 31 08:06:44 GMT 2011

Hello WanMil,

thanks for the details regarding the algorithmn. 

WanMil wrote
> 
>> Two ideas:
>> 1) Optimization:
>> It might save time if we could pass a function pointer to the quadtree.
>> The
>> function does the tagging for one element, and we don't have to manage
>> resultlists. I implemented that, but the program was slower. I assume
>> that
>> was caused by the fact that I did not implement the part that removes
>> elements from the quadtree when they were "fully worked out".
> 
> I am not sure if managing the resultlists is slow. In the end it 
> consists of adding elements to a HashSet (which I think should be quite 
> fast?!)
> 
Well, sometimes the resultlist is quite big, e.g. 50% of all nodes in the
quadtree. This involves some rehashing etc. These actions appear first in my
java.hprof.
Anyway, it will not give a performance boost to change that, only a few
percent.

>> 2) An completely different approach:
>> I did not yet fully understand the algorithmn in LocationHook, but I got
>> the
>> impression that it might be possible to create a dictionary with
>> combinations of admin-level tags, and save a reference to that dictionary
>> instead of adding similar tags to each element. This could save space and
>> time, but would require additional logic in class Element. Do you think
>> this
>> is worth trying?
> 
> Of course you can try although I don't expect that it will improve much.
> 
I have to collect some numbers first to be sure about it.  
The dictionary that I have in mind is more or less what is kept in 
List<Boundary> boundaries 

What I don't understand yet regarding LocationHook is that most elements are
NOT fully worked out after they appeared 1st in a result list. I'll
investigate that today. If any element was worked out after the first time,
we simply could save a reference to the entry in the boundary list instead
of creating result lists and adding similar tags to many elements. 

Gerd

--
View this message in context: http://gis.638310.n2.nabble.com/PATCH-v1-LocationHook-speedup-tp7135704p7139804.html
Sent from the Mkgmap Development mailing list archive at Nabble.com.