Performance of find methods, comparison with linear search

[Renaud Detry]

Hello Paul,

> 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_iterative_linear_find_nearest]: 0s (0 clock  
> ticks)

> Note, lap_iterative_linear_find_nearest resulted in zero clock ticks!
> wtf?

I think it would be a good thing to check what the clock() call
returns before and after the lap_iterative_linear_find_nearest code
bit, to be sure the problem isn't coming from the Stopwatch class.

Btw, the output I get is

$ ./test_kdtree 100000 1000 2>|/dev/null
N: 100000
N_PROBES: 1000
Range: 2.15443
<Stopwatch> kdtree [lap_building_vectors]: 0.01s (1 clock ticks)
<Stopwatch> kdtree [lap_building_tree]: 0.17s (17 clock ticks)
<Stopwatch> kdtree [lap_find_within_range]: 0.02s (2 clock ticks)
Mean count 7
<Stopwatch> kdtree [lap_count_within_range]: 0.01s (1 clock ticks)
<Stopwatch> kdtree [lap_find_nearest]: 0.53s (53 clock ticks)
<Stopwatch> kdtree [lap_optimizing]: 0.73s (73 clock ticks)
<Stopwatch> kdtree [lap_find_within_range_opt]: 0.01s (1 clock ticks)
Mean count 7
<Stopwatch> kdtree [lap_count_within_range_opt]: 0.01s (1 clock ticks)
<Stopwatch> kdtree [lap_find_nearest_opt]: 0.83s (83 clock ticks)
<Stopwatch> kdtree [lap_iterative_linear_find_within_range]: 0.57s  
(57 clock ticks)
<Stopwatch> kdtree [lap_iterative_linear_find_nearest]: 0.04s (4  
clock ticks)
<Stopwatch> kdtree [lap_recursive_linear]: 4.1s (410 clock ticks)

Renaud.