AW's kd-tree
I suggest you stop worrying about how fast a particular kd-tree is and just use one of them. The top few kd-trees are all very similar in performance and I am sure each have their pro's and cons. I personally still use Rednaxela's Gen 2 tree because of how self contained it is (vs his Gen 3 which has more structure).
If you were using it for Robocode I don't think you'd be worrying about which one. What are you using the tree for?
The tree that I have, is approximately as fast as rednaxela's 2nd gen. (slightly faster in my tests). Are you trying to write a kd-tree or just looking for one to use? As far as I know, jk's tree, rednaxela's tree, and my tree are all quite similar. Bucket kd-tree. No recursive search methods. Use a MBR (minimum bounding rectangle). Use a heap to store the points. I think rednaxela was the first to introduce most of those ideas to robocode, but in my tests, mine was slightly faster and presumably the same can be said of JK's tests.
You do not have permission to edit this page, for the following reasons:
You can view and copy the source of this page.
Return to Thread:User talk:Tmservo/gilgalad's kd-tree/reply (5).
Soooo, I've been staying out of this because I have nothing constructive to offer... But FYI, the fact you ignore pretty much every question someone asks makes you seem suspicious. And asking/demanding things without listening makes you seem rude.
If you'd engage in a conversation and tell us your situation, we could probably offer you a lot more help. If you're doing something shady, like cheating on homework, and that's why you're being so secretive, we probably don't want to help.
If that's your goal, why don't you benchmark them instead of asking us things we don't know?
What will you be using the results of the benchmark for? Once you do know which Kd-Tree is fastest, what will you do with it?
What have you done so far? Do you have the kd-tree benchmark running? Did you get JK's tree working with that? Did you get mine working with that? If you want to benchmark them, I think it makes more sense for you to ask for help with that, rather than asking how fast the various trees are (which nobody knows since we never bothered to benchmark all of the latest trees). I'm actually kind of curious about this too, so I'm willing to offer some help if you'll explain what you need done and what you've tried already.
