User talk:AW/kD-Tree

Happy Easter! I have written my recursionless tree, but I am getting unexpected results (My tree is faster than rednaxela's by an unbelievable margin, and the results are different in robocode) I haven't been able figure this out and I am wondering if I am using rednaxela's tree incorrectly? Here is my tester class:

package tree;

import ags.utils.KdTree.SqrEuclid;

public class KDTreeTester {
	static KDTree gunTree = new KDTree(8);
	static SqrEuclid<double[]> AgsTree = new SqrEuclid<double[]>(8, 400000);
	
	public static void main(String[] args) {
		int numOfPoints = 40000;
		long startTime = System.nanoTime();
		 for(int i = 1; i < numOfPoints; i++) {
			 DataPoint addPoint = new DataPoint(8, i);
			 addPoint.setCoordinates(0, Math.random());
			 addPoint.setCoordinates(1, Math.random());
			 addPoint.setCoordinates(2, Math.random());
			 addPoint.setCoordinates(3, Math.random());
			 addPoint.setCoordinates(4, Math.random());
			 addPoint.setCoordinates(5, Math.random());
			 addPoint.setCoordinates(6, Math.random());
			 addPoint.setCoordinates(7, Math.random());
			 gunTree.addPoint(addPoint);
			 }
			 DataPoint SearchPoint = new DataPoint(8, 50);
			 SearchPoint.setCoordinates(0, 0.2);
			 SearchPoint.setCoordinates(1, 0.1);
			 SearchPoint.setCoordinates(2, 0.6);
			 SearchPoint.setCoordinates(3, 0.9);
			 SearchPoint.setCoordinates(4, 0.2);
			 SearchPoint.setCoordinates(5, 0.7);
			 SearchPoint.setCoordinates(6, 0.3);
			 SearchPoint.setCoordinates(7, 0.5);
			
			 System.out.println("time elapsed building = " + ((System.nanoTime() -
			 startTime) * (1E-6)) + " milliseconds");
			 startTime = System.nanoTime();
//			  out.println(gunTree.getNearestNeighbor(SearchPoint).angle);
			 
//			 out.println(gunTree.getNearestNeighbor(SearchPoint).getDistance(SearchPoint));
			
			 gunTree.getNearestNeighbor(SearchPoint);
			 System.out.println("time elapsed searching= " + ((System.nanoTime() -
			 startTime) * (1E-6)));
			 
			 
//			 
//			 
//			 
			 startTime = System.nanoTime();
				
			 for(int i = 1; i < numOfPoints; i++) {
			 double[] addPoint = new double[8];
			 addPoint[0] = Math.random();
			 addPoint[1] = Math.random();
			 addPoint[2] = Math.random();
			 addPoint[3] = Math.random();
			 addPoint[4] = Math.random();
			 addPoint[5] = Math.random();
			 addPoint[6] = Math.random();
			 addPoint[7] = Math.random();
			 
			 double[] trash = new double[1];
			trash[0] = 0.589;
			 
			 AgsTree.addPoint(addPoint, trash);
			 }
			
			 double[] AgsSearchPoint = new double[8];
			 AgsSearchPoint[0] = 0.4;
			 AgsSearchPoint[1] = 0.5;
			 AgsSearchPoint[2] = 0.8;
			 AgsSearchPoint[3] = 0.2;
			 AgsSearchPoint[4] = 0.4;
			 AgsSearchPoint[5] = 0.2;
			 AgsSearchPoint[6] = 0.1;
			 AgsSearchPoint[7] = 0.9;
			
			
			 System.out.println("time elapsed building = " + ((System.nanoTime() -
			 startTime) * (1E-6)) + " milliseconds");
			 startTime = System.nanoTime();
//			  out.println(gunTree.getNearestNeighbor(SearchPoint).angle);
//			 
//			 out.println(gunTree.getNearestNeighbor(SearchPoint).getDistance(SearchPoint));
			
			 AgsTree.nearestNeighbor(AgsSearchPoint, 1, false);
			 System.out.println("time elapsed searching= " + ((System.nanoTime() -
			 startTime) * (1E-6)));
	}
}

Thanks and God bless you, --AW 21:22, 24 April 2011 (UTC)

Well, you're not using my tree incorrectly except that "new SqrEuclid<double[]>(8, 400000);" should probably be "new SqrEuclid<double[]>(8, null);". The second parameter is only used when size-limited trees are desired, and that has extra processing overhead. That probably doesn't make a big different though.

You are however only timing one single run of the search, and that's rather poor test methodology, particularly with how Java's JIT compiler works. The first run of any piece of code will always be slow, because Java's JIT compiler only optimizes after later runs of methods. I don't expect my code to perform well when testing with such an unrealistically small number of searches. I'd highly suggest running the code from the "get source" link here. The framework has been well-tested to test both speed and accuracy of trees in conditions similar to normal use in Robocode. It also has code to allow two modes:

1. Run "dummy" runs that "don't count" first, to let the JIT complier finish with everything. This eliminates the effect of the JIT's delay from the test
2. Run each test iteration in a new JVM. This ensures every iteration is equally influenced by the JIT on average.

When benchmarking in Java, one really needs to be careful to consider the influence of the JIT compiler, as it can radically sway the results. Even if it weren't for that you still need thousands of searches for an accurate speed measurement.

I'd also wonder if you've tested the accuracy of your kd-tree. It can be very easy to have some kinds of bugs that dramatically improve speed but lead to incorrect output on occasion.

--Rednaxela 00:41, 25 April 2011 (UTC)

Firstly, thanks for having me check the accuracy of my tree. I have now fixed that, and assuming I didn't break it again while optimizing I think I have the fastest kD-Tree without bounding boxes, but my tree is slower than yours:

AW time (milliseconds per point) = 0.23410419200000002

AW visits = 1018805

AGS time (milliseconds per point) = 0.15207064

AGS visits = 403029

As you can see, the problem is that yours visits fewer leaf nodes than mine, due to the fact that you have the bounding box. I'll see how I can do when I add that to my tree. Also, I haven't been able to get the KNN-benchmark running on my computer, not that I have tried hard, but that's why I am using my own benchmark here (10,000 iterations with 200 discarded first). --AW 17:57, 28 April 2011 (UTC)