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


Generated on OURCE_DATE_EPOCH for elastix by doxygen 1.8.18 elastix logo