KDTreeF

Jump to navigation Jump to search
K-NEAREST NEIGHBOURS ALGORITHMS BENCHMARK
-----------------------------------------
Reading data from gun-data-Diamond-vs-jk.mini.CunobelinDC 0.3.csv.gz
Read 25621 saves and 10300 searches.

Running 20 repetition(s) for k-nearest neighbours searching:
:: 13 dimension(s); 10 neighbour(s)

RESULT << k-nearest neighbours search with Chase-san's kd-tree (KDTreeC) >>
: Average searching time       = 0.0776 miliseconds
: Average worst searching time = 11.1474 miliseconds
: Average adding time          = 1.5965 microseconds
: Accuracy                     = 100.0%

RESULT << k-nearest neighbours search with Chase-san's kd-tree (KDTreeF) >>
: Average searching time       = 0.0259 miliseconds
: Average worst searching time = 1.0691 miliseconds
: Average adding time          = 1.5182 microseconds
: Accuracy                     = 100.0%

RESULT << k-nearest neighbours search with duyn's basic kd-tree >>
: Average searching time       = 0.2016 miliseconds
: Average worst searching time = 10.4197 miliseconds
: Average adding time          = 0.8725 microseconds
: Accuracy                     = 100.0%

RESULT << k-nearest neighbours search with duyn's fast kd-tree >>
: Average searching time       = 0.0245 miliseconds
: Average worst searching time = 10.5265 miliseconds
: Average adding time          = 3.4632 microseconds
: Accuracy                     = 100.0%

RESULT << k-nearest neighbours search with duyn's optimised kd-tree >>
: Average searching time       = 0.0264 miliseconds
: Average worst searching time = 13.8944 miliseconds
: Average adding time          = 3.4938 microseconds
: Accuracy                     = 100.0%

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

RESULT << k-nearest neighbours search with Nat's Bucket PR k-d tree >>
: Average searching time       = 0.2280 miliseconds
: Average worst searching time = 188.3711 miliseconds
: Average adding time          = 27.4455 microseconds
: Accuracy                     = 27.12%

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

RESULT << k-nearest neighbours search with Rednaxela's kd-tree (3rd gen, iterated) >>
: Average searching time       = 0.0183 miliseconds
: Average worst searching time = 11.8064 miliseconds
: Average adding time          = 1.9969 microseconds
: Accuracy                     = 100.0%

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

RESULT << k-nearest neighbours search with Simonton's Bucket PR k-d tree >>
: Average searching time       = 0.1336 miliseconds
: Average worst searching time = 12.6894 miliseconds
: Average adding time          = 4.1237 microseconds
: Accuracy                     = 100.0%

RESULT << k-nearest neighbours search with Voidious' Bucket PR k-d tree >>
: Average searching time       = 0.1115 miliseconds
: Average worst searching time = 8.2543 miliseconds
: Average adding time          = 2.2128 microseconds
: Accuracy                     = 100.0%


BEST RESULT: 
 - #1 Rednaxela's kd-tree (3rd gen) [0.0155]
 - #2 Rednaxela's kd-tree (2nd gen) [0.0183]
 - #3 Rednaxela's kd-tree (3rd gen, iterated) [0.0183]
 - #4 duyn's fast kd-tree [0.0245]
 - #5 Chase-san's kd-tree (KDTreeF) [0.0259]
 - #6 duyn's optimised kd-tree [0.0264]
 - #7 Chase-san's kd-tree (KDTreeC) [0.0776]
 - #8 Voidious' Bucket PR k-d tree [0.1115]
 - #9 Simonton's Bucket PR k-d tree [0.1336]
 - #10 duyn's basic kd-tree [0.2016]
 - #11 Nat's Bucket PR k-d tree [0.2280]
 - #12 Voidious' Linear search [0.4874]

Benchmark running time: 450.15 seconds

KDTreeFGraph.png

Really managed to hammer down the worst average time. As well as 1/3rd the best time. Still not really on par with Rednaxela's tree though.

Chase-san06:08, 9 June 2012

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.

Rednaxela21:02, 9 June 2012

You do not have permission to edit this page, for the following reasons:

  • The action you have requested is limited to users in the group: Users.
  • You must confirm your email address before editing pages. Please set and validate your email address through your user preferences.

You can view and copy the source of this page.

Return to Thread:User talk:Chase-san/Kd-Tree/KDTreeF/reply (2).