Performance of find methods, comparison with linear search

[Paul Harris]

Hi Renaud,

I had a look at the test, but I got this result:

$ ./test_kdtree 100000 1000
N: 100000
N_PROBES: 1000
Range: 2.15443
N = [ N 100000 ];
N_PROBES = [ N_PROBES 1000 ];
<Stopwatch> kdtree [lap_building_vectors]: 0.03s (30000 clock ticks)
lap_building_vectors = [ lap_building_vectors 30000 ];
<Stopwatch> kdtree [lap_building_tree]: 0.12s (120000 clock ticks)
lap_building_tree = [ lap_building_tree 120000 ];
<Stopwatch> kdtree [lap_find_within_range]: 0.02s (20000 clock ticks)
lap_find_within_range = [ lap_find_within_range 20000 ];
Mean count 7
<Stopwatch> kdtree [lap_count_within_range]: 0.02s (20000 clock ticks)
lap_count_within_range = [ lap_count_within_range 20000 ];
<Stopwatch> kdtree [lap_find_nearest]: 1.12s (1120000 clock ticks)
lap_find_nearest = [ lap_find_nearest 1.12e+06 ];
<Stopwatch> kdtree [lap_optimizing]: 0.69s (690000 clock ticks)
lap_optimizing = [ lap_optimizing 690000 ];
<Stopwatch> kdtree [lap_find_within_range_opt]: 0.01s (10000 clock ticks)
lap_find_within_range_opt = [ lap_find_within_range_opt 10000 ];
Mean count 7
<Stopwatch> kdtree [lap_count_within_range_opt]: 0.01s (10000 clock ticks)
lap_count_within_range_opt = [ lap_count_within_range_opt 10000 ];
<Stopwatch> kdtree [lap_find_nearest_opt]: 0.8s (800000 clock ticks)
lap_find_nearest_opt = [ lap_find_nearest_opt 800000 ];
<Stopwatch> kdtree [lap_iterative_linear_find_within_range]: 0.71s (710000 clock
 ticks)
lap_iterative_linear_find_within_range = [ lap_iterative_linear_find_within_rang
e 710000 ];
<Stopwatch> kdtree [lap_iterative_linear_find_nearest]: 0s (0 clock ticks)
lap_iterative_linear_find_nearest = [ lap_iterative_linear_find_nearest 0 ];
<Stopwatch> kdtree [lap_recursive_linear]: 3.72s (3720000 clock ticks)
lap_recursive_linear = [ lap_recursive_linear 3.72e+06 ];


Note, lap_iterative_linear_find_nearest resulted in zero clock ticks!
wtf?   I added 2 int counters to increment each time (a) a closer item
was found and (b) after each 'test'.   Then it gave more reasonable
results, like 0.6s.

thanks,
Paul