1 | //---------------------------------------------------------------------- |
---|
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 |
---|