Statistics
| Branch: | Revision:

root / rgbdslam / gicp / ann_1.1.1 / include / ANN / ANNperf.h @ 9240aaa3

History | View | Annotate | Download (8.01 KB)

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