root / rgbdslam / gicp / ann_1.1.1 / include / ANN / ANNperf.h @ 9240aaa3
History | View | Annotate | Download (8.01 KB)
1 | 9240aaa3 | Alex | //----------------------------------------------------------------------
|
---|---|---|---|
2 | // File: ANNperf.h
|
||
3 | // Programmer: Sunil Arya and David Mount
|
||
4 | // Last modified: 03/04/98 (Release 0.1)
|
||
5 | // Description: Include file for ANN performance stats
|
||
6 | //
|
||
7 | // Some of the code for statistics gathering has been adapted
|
||
8 | // from the SmplStat.h package in the g++ library.
|
||
9 | //----------------------------------------------------------------------
|
||
10 | // Copyright (c) 1997-2005 University of Maryland and Sunil Arya and
|
||
11 | // David Mount. All Rights Reserved.
|
||
12 | //
|
||
13 | // This software and related documentation is part of the Approximate
|
||
14 | // Nearest Neighbor Library (ANN). This software is provided under
|
||
15 | // the provisions of the Lesser GNU Public License (LGPL). See the
|
||
16 | // file ../ReadMe.txt for further information.
|
||
17 | //
|
||
18 | // The University of Maryland (U.M.) and the authors make no
|
||
19 | // representations about the suitability or fitness of this software for
|
||
20 | // any purpose. It is provided "as is" without express or implied
|
||
21 | // warranty.
|
||
22 | //----------------------------------------------------------------------
|
||
23 | // History:
|
||
24 | // Revision 0.1 03/04/98
|
||
25 | // Initial release
|
||
26 | // Revision 1.0 04/01/05
|
||
27 | // Added ANN_ prefix to avoid name conflicts.
|
||
28 | //----------------------------------------------------------------------
|
||
29 | |||
30 | #ifndef ANNperf_H
|
||
31 | #define ANNperf_H
|
||
32 | |||
33 | //----------------------------------------------------------------------
|
||
34 | // basic includes
|
||
35 | //----------------------------------------------------------------------
|
||
36 | |||
37 | #include <ANN/ANN.h> // basic ANN includes |
||
38 | |||
39 | //----------------------------------------------------------------------
|
||
40 | // kd-tree stats object
|
||
41 | // This object is used for collecting information about a kd-tree
|
||
42 | // or bd-tree.
|
||
43 | //----------------------------------------------------------------------
|
||
44 | |||
45 | class ANNkdStats { // stats on kd-tree
|
||
46 | public:
|
||
47 | int dim; // dimension of space |
||
48 | int n_pts; // no. of points |
||
49 | int bkt_size; // bucket size |
||
50 | int n_lf; // no. of leaves (including trivial) |
||
51 | int n_tl; // no. of trivial leaves (no points) |
||
52 | int n_spl; // no. of splitting nodes |
||
53 | int n_shr; // no. of shrinking nodes (for bd-trees) |
||
54 | int depth; // depth of tree |
||
55 | float sum_ar; // sum of leaf aspect ratios |
||
56 | float avg_ar; // average leaf aspect ratio |
||
57 | //
|
||
58 | // reset stats
|
||
59 | void reset(int d=0, int n=0, int bs=0) |
||
60 | { |
||
61 | dim = d; n_pts = n; bkt_size = bs; |
||
62 | n_lf = n_tl = n_spl = n_shr = depth = 0;
|
||
63 | sum_ar = avg_ar = 0.0; |
||
64 | } |
||
65 | |||
66 | ANNkdStats() // basic constructor
|
||
67 | { reset(); } |
||
68 | |||
69 | void merge(const ANNkdStats &st); // merge stats from child |
||
70 | }; |
||
71 | |||
72 | //----------------------------------------------------------------------
|
||
73 | // ANNsampStat
|
||
74 | // A sample stat collects numeric (double) samples and returns some
|
||
75 | // simple statistics. Its main functions are:
|
||
76 | //
|
||
77 | // reset() Reset to no samples.
|
||
78 | // += x Include sample x.
|
||
79 | // samples() Return number of samples.
|
||
80 | // mean() Return mean of samples.
|
||
81 | // stdDev() Return standard deviation
|
||
82 | // min() Return minimum of samples.
|
||
83 | // max() Return maximum of samples.
|
||
84 | //----------------------------------------------------------------------
|
||
85 | class DLL_API ANNsampStat { |
||
86 | int n; // number of samples |
||
87 | double sum; // sum |
||
88 | double sum2; // sum of squares |
||
89 | double minVal, maxVal; // min and max |
||
90 | public : |
||
91 | void reset() // reset everything |
||
92 | { |
||
93 | n = 0;
|
||
94 | sum = sum2 = 0;
|
||
95 | minVal = ANN_DBL_MAX; |
||
96 | maxVal = -ANN_DBL_MAX; |
||
97 | } |
||
98 | |||
99 | ANNsampStat() { reset(); } // constructor
|
||
100 | |||
101 | void operator+=(double x) // add sample |
||
102 | { |
||
103 | n++; sum += x; sum2 += x*x; |
||
104 | if (x < minVal) minVal = x;
|
||
105 | if (x > maxVal) maxVal = x;
|
||
106 | } |
||
107 | |||
108 | int samples() { return n; } // number of samples |
||
109 | |||
110 | double mean() { return sum/n; } // mean |
||
111 | |||
112 | // standard deviation
|
||
113 | double stdDev() { return sqrt((sum2 - (sum*sum)/n)/(n-1));} |
||
114 | |||
115 | double min() { return minVal; } // minimum |
||
116 | double max() { return maxVal; } // maximum |
||
117 | }; |
||
118 | |||
119 | //----------------------------------------------------------------------
|
||
120 | // Operation count updates
|
||
121 | //----------------------------------------------------------------------
|
||
122 | |||
123 | #ifdef ANN_PERF
|
||
124 | #define ANN_FLOP(n) {ann_Nfloat_ops += (n);}
|
||
125 | #define ANN_LEAF(n) {ann_Nvisit_lfs += (n);}
|
||
126 | #define ANN_SPL(n) {ann_Nvisit_spl += (n);}
|
||
127 | #define ANN_SHR(n) {ann_Nvisit_shr += (n);}
|
||
128 | #define ANN_PTS(n) {ann_Nvisit_pts += (n);}
|
||
129 | #define ANN_COORD(n) {ann_Ncoord_hts += (n);}
|
||
130 | #else
|
||
131 | #define ANN_FLOP(n)
|
||
132 | #define ANN_LEAF(n)
|
||
133 | #define ANN_SPL(n)
|
||
134 | #define ANN_SHR(n)
|
||
135 | #define ANN_PTS(n)
|
||
136 | #define ANN_COORD(n)
|
||
137 | #endif
|
||
138 | |||
139 | //----------------------------------------------------------------------
|
||
140 | // Performance statistics
|
||
141 | // The following data and routines are used for computing performance
|
||
142 | // statistics for nearest neighbor searching. Because these routines
|
||
143 | // can slow the code down, they can be activated and deactiviated by
|
||
144 | // defining the ANN_PERF variable, by compiling with the option:
|
||
145 | // -DANN_PERF
|
||
146 | //----------------------------------------------------------------------
|
||
147 | |||
148 | //----------------------------------------------------------------------
|
||
149 | // Global counters for performance measurement
|
||
150 | //
|
||
151 | // visit_lfs The number of leaf nodes visited in the
|
||
152 | // tree.
|
||
153 | //
|
||
154 | // visit_spl The number of splitting nodes visited in the
|
||
155 | // tree.
|
||
156 | //
|
||
157 | // visit_shr The number of shrinking nodes visited in the
|
||
158 | // tree.
|
||
159 | //
|
||
160 | // visit_pts The number of points visited in all the
|
||
161 | // leaf nodes visited. Equivalently, this
|
||
162 | // is the number of points for which distance
|
||
163 | // calculations are performed.
|
||
164 | //
|
||
165 | // coord_hts The number of times a coordinate of a
|
||
166 | // data point is accessed. This is generally
|
||
167 | // less than visit_pts*d if partial distance
|
||
168 | // calculation is used. This count is low
|
||
169 | // in the sense that if a coordinate is hit
|
||
170 | // many times in the same routine we may
|
||
171 | // count it only once.
|
||
172 | //
|
||
173 | // float_ops The number of floating point operations.
|
||
174 | // This includes all operations in the heap
|
||
175 | // as well as distance calculations to boxes.
|
||
176 | //
|
||
177 | // average_err The average error of each query (the
|
||
178 | // error of the reported point to the true
|
||
179 | // nearest neighbor). For k nearest neighbors
|
||
180 | // the error is computed k times.
|
||
181 | //
|
||
182 | // rank_err The rank error of each query (the difference
|
||
183 | // in the rank of the reported point and its
|
||
184 | // true rank).
|
||
185 | //
|
||
186 | // data_pts The number of data points. This is not
|
||
187 | // a counter, but used in stats computation.
|
||
188 | //----------------------------------------------------------------------
|
||
189 | |||
190 | extern int ann_Ndata_pts; // number of data points |
||
191 | extern int ann_Nvisit_lfs; // number of leaf nodes visited |
||
192 | extern int ann_Nvisit_spl; // number of splitting nodes visited |
||
193 | extern int ann_Nvisit_shr; // number of shrinking nodes visited |
||
194 | extern int ann_Nvisit_pts; // visited points for one query |
||
195 | extern int ann_Ncoord_hts; // coordinate hits for one query |
||
196 | extern int ann_Nfloat_ops; // floating ops for one query |
||
197 | extern ANNsampStat ann_visit_lfs; // stats on leaf nodes visits |
||
198 | extern ANNsampStat ann_visit_spl; // stats on splitting nodes visits |
||
199 | extern ANNsampStat ann_visit_shr; // stats on shrinking nodes visits |
||
200 | extern ANNsampStat ann_visit_nds; // stats on total nodes visits |
||
201 | extern ANNsampStat ann_visit_pts; // stats on points visited |
||
202 | extern ANNsampStat ann_coord_hts; // stats on coordinate hits |
||
203 | extern ANNsampStat ann_float_ops; // stats on floating ops |
||
204 | //----------------------------------------------------------------------
|
||
205 | // The following need to be part of the public interface, because
|
||
206 | // they are accessed outside the DLL in ann_test.cpp.
|
||
207 | //----------------------------------------------------------------------
|
||
208 | DLL_API extern ANNsampStat ann_average_err; // average error |
||
209 | DLL_API extern ANNsampStat ann_rank_err; // rank error |
||
210 | |||
211 | //----------------------------------------------------------------------
|
||
212 | // Declaration of externally accessible routines for statistics
|
||
213 | //----------------------------------------------------------------------
|
||
214 | |||
215 | DLL_API void annResetStats(int data_size); // reset stats for a set of queries |
||
216 | |||
217 | DLL_API void annResetCounts(); // reset counts for one queries |
||
218 | |||
219 | DLL_API void annUpdateStats(); // update stats with current counts |
||
220 | |||
221 | DLL_API void annPrintStats(ANNbool validate); // print statistics for a run |
||
222 | |||
223 | #endif |