Slow K-d tree implementation

[hoerup]

Just wanted to let you know that your K-d tree implementation is very very slow compared to eg the one from https://github.com/AReallyGoodName/OfflineReverseGeocode

[phishman3579]

From the readme of this site "The code isn't overly-optimized but is written to be correct and readable."

In other words, I know. The code is meant to be more readable than performant.

[phishman3579]

@hoerup I did a quick test and I am seeing similar performance between the two implementations with my implementation quite a bit quicker than Geocode at nearest neighbor search. Can you show me what you did to test the performance?

Data Structure (25600 items)	Add time	NNS time
My KdTree	39.58 ms	70.43 ms
GeoCode KdTree	35.69 ms	243.15 ms

Testing code below...

my kd tree construction time.

        long beforeAddTime = System.nanoTime();
        KdTree<KdTree.XYZPoint> tree = new KdTree<KdTree.XYZPoint>(points, 2); // 2 since we only care about two dimensions (x,y) 
        long afterAddTime = System.nanoTime();

Geocode construction time

        long beforeAddTime = System.nanoTime();
        KDTree<XYZPoint> tree = new KDTree<XYZPoint>(points); 
        long afterAddTime = System.nanoTime();

My NNS time:

        long beforeContainsTime = System.nanoTime();
        for (KdTree.XYZPoint p : points) {
            //boolean r = tree.contains(p);
            Collection<KdTree.XYZPoint> r = tree.nearestNeighbourSearch(1, p);
            assertTrue("Point not found.", p, tree, (r.size()==1 && r.iterator().next().equals(p)));
        }
        long afterContainsTime = System.nanoTime();

GeoCode NNS time:

        long beforeContainsTime = System.nanoTime();
        for (XYZPoint p : points) {
            XYZPoint r = tree.findNearest(p);
            assertTrue("Point not found.", p, tree, r.equals(p));
        }
        long afterContainsTime = System.nanoTime();

All times measured via ((after-before)/points)