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