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 ma 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)

i don't see the KD-TREE

The tree's code is in Gilgalad (these tests weren't run with the latest version anyways)

I was working on my kd-tree and one of the changes I made was to store the data in the tree rather than in a hashmap, thinking that this would save time. However, in my benchmarks, it is much faster to use a hashmap. Does anyone know why this would be the case?

It's very strange question because hashmap and kd tree is absolutly different structures with different aims and contract and for sure map faster because it's nature. May be you publish source code with usage of map and tree?

O, looks like i misunderstand you. Do you mean why HashMap is faster than TreeMap? I'm not sure but i think, that hash map has efficiency O(1) but tree map O(log N) because tree map are sorted and based on red-black tree. I do not describe how they works because my english skill...

What I mean is that it seems slower to store the data with the point in a KDTree than it does to store the point in the tree and then use the point as the key for the hashmap. So for example you would have:

PointEntry entry = new PointEntry(pointCoordinates, DataObject); tree.add(entry);

instead of

hashmap.add(pointCoordinates, DataObject); tree.add(pointCoordinates);

Maybe I have some typecasting in the tree that is slowing it down?

Ok, i understand yours problem. But now i have not advices:) can you publish kdtree? Is difference only in type of data stored in kdtree? What type has pointCoordinates?

IIRC, my experience on this matter is that it's faster to use HashMap than to store PointEntry objects that have both pointCoordinates and DataObject, but it's faster than either to in your leaf nodes store two arrays, one for the "pointCoordinates" values and one for the "dataObject" values.

I'm pretty sure the reason for this is that with both using a HashMap for data objects, and using two separate arrays for coordinates and data, you avoid some pointer dereferencing. Basically, it's bad for performance if when comparing the location of a point, you have to dereference a PointEntry object and the coordinates themselves, rather than just the coordinates.

One of the important things to remember when dealing with Java, is that unlike some other languages (i.e. C++) every object is another pointer you have to dereference, which makes an array of primitives faster than an array of objects, and also makes two arrays of objects faster than one array of objects that store two objects each.