Performance of find methods, comparison with linear search

[Paul Harris]

Hi,

Briefly, I like this new algorithm, but I think there is room for
improvement...  read on.


To test it with test_kdtree, first add these three lines to kdtree.hpp
after every call to _M_sq_distance()
#ifdef KDTREE_CHECK_PERFORMANCE
        ++num_dist_calcs;
#endif

I also added some counters to count how many times each node was
compared.  See attached file.


See also attached, test_kdtree.cpp, which adds a test for
find_nearest_iterative().

YOU SHOULD comment out the first line of test_kdtree.cpp if you are
going to run the test with more than 1 probe.
The first line is #define KDTREE_CHECK_PERFORMANCE_COUNTERS.
If you run more than 1 probe, it will print out lots of rubbish.  Read
on for why this line is useful at all...



The results are impressive, and seem to indicate that optimize() IS
doing its job correctly.  But optimize only benefits the new
algorithm, not the old.