Thread history

Ah, looks like KNN.jar that's uploaded on the wiki isn't quite 100% up-to-date. A couple days after the KNN.jar uploaded to the wiki was last updated I made a few minor changes. See here for the latest source [1]

You got that just in time, your latest code is now in!

So on the vanilla Diamond-gun data benchmark it seems to be pretty much tied with your Gen2 and Gen3, changing places from run to run. This is what I saw mostly though, your Gen2 slightly above Gen3, and my cache-hit tree in the middle:

BEST RESULT: 
 - #1 Rednaxela's kd-tree (2nd gen) [0.0317]
 - #2 Skilgannon's Cache-hit KDTree [0.0340]
 - #3 Rednaxela's kd-tree (3rd gen) [0.0356]
 - #4 Voidious' Linear search [0.4175]

So, I wrote some code which instantiates, does operations on, then destroys an array of 1k doubles and 1k ints, and makes it a dependency of a later println. This was the result:

RESULT << k-nearest neighbours search with Voidious' Linear search >>
: Average searching time       = 0.4198 miliseconds
: Average worst searching time = 14.7468 miliseconds
: Average adding time          = 1.6292 microseconds
: Accuracy                     = 100.0%

RESULT << k-nearest neighbours search with Rednaxela's kd-tree (2nd gen) >>
: Average searching time       = 0.0333 miliseconds
: Average worst searching time = 1.7135 miliseconds
: Average adding time          = 1.7662 microseconds
: Accuracy                     = 100.0%

RESULT << k-nearest neighbours search with Skilgannon's Cache-hit KDTree >>
: Average searching time       = 0.0312 miliseconds
: Average worst searching time = 1.3695 miliseconds
: Average adding time          = 2.7642 microseconds
: Accuracy                     = 100.0%

RESULT << k-nearest neighbours search with Rednaxela's kd-tree (3rd gen) >>
: Average searching time       = 0.0317 miliseconds
: Average worst searching time = 1.2998 miliseconds
: Average adding time          = 2.1558 microseconds
: Accuracy                     = 100.0%


BEST RESULT: 
 - #1 Skilgannon's Cache-hit KDTree [0.0312]
 - #2 Rednaxela's kd-tree (3rd gen) [0.0317]
 - #3 Rednaxela's kd-tree (2nd gen) [0.0333]
 - #4 Voidious' Linear search [0.4198]

It now comes first every single time I run. So it seems my cache-hit design has paid off (slightly) =)

Ahhh neat. Hmm... having had a quick look at your code earlier today, I'm feeling a little tempted to add some cache-behavior optimizations to my tree... oh wow... just realized it's been 3 years since I touched it.

Feel free to port it to Lua while you're at it... :-) Just kidding, but fyi I might sometime. The first time I tried to write a BerryBots gun and realized I didn't have a kd-tree to work with was sobering. :-)