queso-0.57.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Pages
ANNperf.h
Go to the documentation of this file.
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
DLL_API ANNsampStat ann_rank_err
Definition: perf.cpp:65
void operator+=(double x)
Definition: ANNperf.h:101
double minVal
Definition: ANNperf.h:89
ANNsampStat ann_visit_nds
Definition: perf.cpp:59
int n_pts
Definition: ANNperf.h:48
DLL_API void annResetStats(int data_size)
Definition: perf.cpp:71
int ann_Ncoord_hts
Definition: perf.cpp:54
float sum_ar
Definition: ANNperf.h:55
int depth
Definition: ANNperf.h:54
int ann_Nvisit_shr
Definition: perf.cpp:52
double mean()
Definition: ANNperf.h:110
ANNbool validate
Definition: ann_test.cpp:489
int ann_Nvisit_pts
Definition: perf.cpp:53
DLL_API void annUpdateStats()
Definition: perf.cpp:95
int data_size
Definition: ann_test.cpp:473
int n_tl
Definition: ANNperf.h:51
int samples()
Definition: ANNperf.h:108
DLL_API ANNsampStat ann_average_err
Definition: perf.cpp:64
int ann_Nfloat_ops
Definition: perf.cpp:55
int ann_Ndata_pts
Definition: perf.cpp:49
double stdDev()
Definition: ANNperf.h:113
ANNsampStat ann_visit_shr
Definition: perf.cpp:58
const double ANN_DBL_MAX
Definition: ANN.h:114
ANNsampStat()
Definition: ANNperf.h:99
double max()
Definition: ANNperf.h:116
int dim
Definition: ANNperf.h:47
DLL_API void annPrintStats(ANNbool validate)
Definition: perf.cpp:116
int n_spl
Definition: ANNperf.h:52
void reset(int d=0, int n=0, int bs=0)
Definition: ANNperf.h:59
ANNkdStats()
Definition: ANNperf.h:66
double sum
Definition: ANNperf.h:87
int n_shr
Definition: ANNperf.h:53
int ann_Nvisit_lfs
Definition: perf.cpp:50
ANNsampStat ann_visit_pts
Definition: perf.cpp:60
int bkt_size
Definition: ANNperf.h:49
ANNsampStat ann_visit_spl
Definition: perf.cpp:57
ANNsampStat ann_coord_hts
Definition: perf.cpp:61
ANNsampStat ann_visit_lfs
Definition: perf.cpp:56
double min()
Definition: ANNperf.h:115
int ann_Nvisit_spl
Definition: perf.cpp:51
float avg_ar
Definition: ANNperf.h:56
double sum2
Definition: ANNperf.h:88
void merge(const ANNkdStats &st)
Definition: kd_tree.cpp:133
void reset()
Definition: ANNperf.h:91
ANNbool
Definition: ANN.h:132
DLL_API void annResetCounts()
Definition: perf.cpp:85
ANNsampStat ann_float_ops
Definition: perf.cpp:62
int n_lf
Definition: ANNperf.h:50

Generated on Tue Jun 5 2018 19:48:54 for queso-0.57.1 by  doxygen 1.8.5