View source for User talk:Chase-san/Kd-Tree

NullPointerExceptions and inaccuracy

Trying to test your Kd-Tree in the benchmark framework, I'm getting some NullPointerExceptions due to right.rect.getNearest(k) returning null sometimes. I don't know if it's the proper fix, I changed the relevant lines to be like:

PointKD p = right.rect.getNearest(k);
if(p != null && k.distanceSq(p) < t) {

Something else is wrong also I believe, because it's only getting "88% accuracy" out of the benchmark results, so it's not finding all of the nearest neighbors correctly. --Rednaxela 22:23, 1 March 2010 (UTC)

That should only happen if the rectangle hasn't gotten expanded ever, which shouldn't happen, unless you haven't added anything to the tree at all (darn me and removing all my safeties). Since this gets set during the add. Can you give me some idea of the data you are feeding into it? --Chase 22:44, 1 March 2010 (UTC)

Nice stuff! With that graph, it looks like the place you have the most room to squeeze out more performance if you wish to, is by refactoring the code so that the JIT gets it optimized sooner. Having the lowest time in those first few searches is certainly neat, and perhaps is the most important thing in the robocode context as that's the most likely time for a kd-tree to lead to a skipped turn. I wonder what it took to get that down and how much that is dataset specific.

But on the inverse you have a smaller data set earlier on. So it might balance out to a point. But I do intend to work on that a bit. I actually originally tuned with a random data set.

Also the current tree is based off C but I removed the Item class and altered the return to use a heap. Though I was considering having it interface with SortedMap and just returning that interface. So that I could avoid the issue of defining an external class.

I am mulling around how to redesign my tree so that it works better with the JIT, and so I create/destroy fewer objects (which should save some time).