Regarding PrioQueue
This is the thread's initial revision.
Out of curiosity, have you compared your PrioQueue impelementation that uses binary search, to the heap implementation that I use in my 3rd gen tree? Looking over it, I expect the heap to be faster.
Consider the heapsort algorithm. It is O(n log(n)) to perform the sort like most good sorting algorithms. Roughly half the effort of the heapsort is generating the heap-ordering, and half is generating the fully sorted order from the heap-ordering. This is not exactly what we're doing, but the general idea is that generating heap-ordering is lower cost than generating sorted-ordering, despite both having an O(n log(n)) cost.
With both the heap method and the binary search method, insertions are O(log(n)), except...
- With the heap method, you only generate heap order for items that don't end up within the closest N points. This doesn't change the O(log(n)) characteristic, but it ought to be lower cost.
- Your implementation also has some O(n) characeristics, because inserting in the middle of an ArrayList causes the ArrayList to copy everything after the insertion point. It's a fast O(n) operation when the number of points being returned is small, but I think it's still notable.
You're probably right that the binary search method get's through JIT faster, but I'm unsure if that pays off due to the two disadvantages I note above. In addition, I'd suspect your SearchResult container object probably adds some extra cost to your result queue. When I was doing my heap-based implementation I found it was faster to have an Object[] array for the results and double[] array for distances, and manage both in the heap, rather than using a container.
