[37] | 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 |
---|