Am 31.12.2011 09:06, schrieb GerdP:
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.
The reason is that the boundaries are not complete. Complete in two meanings: 1. Some boundaries are missing due to incomplete OSM data 2. In some areas there might be a boundary with admin_level=7, other areas do not have that admin_level. The LocationHook cannot know about that and therefore it can remove elements only if they contain all remaining tags. WanMil
Gerd