← Back to branch summary

~evarlast/ubuntu/utopic/mongodb/upstart-workaround-debian-bug-718702

« back to all changes in this revision

Viewing changes to src/mongo/util/descriptive_stats.h

  • Committer: Package Import Robot
  • Author(s): James Page, James Page, Robie Basak
  • Date: 2013-05-29 17:44:42 UTC
  • mfrom: (44.1.7 sid)
  • Revision ID: package-import@ubuntu.com-20130529174442-z0a4qmoww4y0t458
Tags: 1:2.4.3-1ubuntu1
[ James Page ]
* Merge from Debian unstable, remaining changes:
  - Enable SSL support:
    + d/control: Add libssl-dev to BD's.
    + d/rules: Enabled --ssl option.
    + d/mongodb.conf: Add example SSL configuration options.
  - d/mongodb-server.mongodb.upstart: Add upstart configuration.
  - d/rules: Don't strip binaries during scons build for Ubuntu.
  - d/control: Add armhf to target archs.
  - d/p/SConscript.client.patch: fixup install of client libraries.
  - d/p/0010-install-libs-to-usr-lib-not-usr-lib64-Closes-588557.patch:
    Install libraries to lib not lib64.
* Dropped changes:
  - d/p/arm-support.patch: Included in Debian.
  - d/p/double-alignment.patch: Included in Debian.
  - d/rules,control: Debian also builds with avaliable system libraries
    now.
* Fix FTBFS due to gcc and boost upgrades in saucy:
  - d/p/0008-ignore-unused-local-typedefs.patch: Add -Wno-unused-typedefs
    to unbreak building with g++-4.8.
  - d/p/0009-boost-1.53.patch: Fixup signed/unsigned casting issue.

[ Robie Basak ]
* d/p/0011-Use-a-signed-char-to-store-BSONType-enumerations.patch: Fixup
  build failure on ARM due to missing signed'ness of char cast.

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/mongo/util/descriptive_stats.h
 
1
/*    Copyright 2012 10gen Inc.
 
2
 *
 
3
 *    Licensed under the Apache License, Version 2.0 (the "License");
 
4
 *    you may not use this file except in compliance with the License.
 
5
 *    You may obtain a copy of the License at
 
6
 *
 
7
 *    http://www.apache.org/licenses/LICENSE-2.0
 
8
 *
 
9
 *    Unless required by applicable law or agreed to in writing, software
 
10
 *    distributed under the License is distributed on an "AS IS" BASIS,
 
11
 *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 
12
 *    See the License for the specific language governing permissions and
 
13
 *    limitations under the License.
 
14
 */
 
15
 
 
16
#pragma once
 
17
 
 
18
#include <cmath>
 
19
 
 
20
#include "mongo/db/jsobj.h"
 
21
#include "mongo/util/assert_util.h"
 
22
 
 
23
/**
 
24
 * These classes provide online descriptive statistics estimator capable
 
25
 * of computing the mean, standard deviation and quantiles.
 
26
 * Exactness is traded for the ability to obtain reasonable estimates
 
27
 * without the need to store all the samples or perform multiple passes
 
28
 * over the data.
 
29
 *
 
30
 * NOTEs on the estimator accessors provide information about accuracy
 
31
 * of the approximation.
 
32
 *
 
33
 * The implementation of the estimators is heavily inspired by the algorithms used in
 
34
 * boost.accumulators (www.boost.org/libs/accumulators/).
 
35
 * It differs by being tailored for typical descriptive statistics use cases
 
36
 * thus providing a simpler (even though less flexible) interface.
 
37
 */
 
38
namespace mongo {
 
39
 
 
40
    /**
 
41
     * Collects count, minimum and maximum, calculates mean and standard deviation.
 
42
     *
 
43
     * The 'Sample' template parameter is the type of the samples. It does not affect the calculated
 
44
     * mean and standard deviation as all values are converted to double. 
 
45
     * However, setting the correct sample type prevents unnecessary casting or precision loss
 
46
     * for min and max.
 
47
     */
 
48
    template <class Sample>
 
49
    class BasicEstimators {
 
50
    public:
 
51
        BasicEstimators();
 
52
 
 
53
        /**
 
54
         * Update estimators with another observed value.
 
55
         */
 
56
        BasicEstimators& operator <<(const Sample sample);
 
57
 
 
58
        /**
 
59
         * @return number of observations so far
 
60
         */
 
61
        inline size_t count() const { return _count; }
 
62
 
 
63
        /**
 
64
         * @return mean of the observations seen so far
 
65
         * NOTE: exact (within the limits of IEEE floating point precision).
 
66
         */
 
67
        inline double mean() const { return _sum / _count; }
 
68
 
 
69
        /**
 
70
         * @return standard deviation of the observations so far
 
71
         * NOTE: exact (within the limits of IEEE floating point precision).
 
72
         */
 
73
        inline double stddev() const { return std::sqrt(_diff / _count); }
 
74
 
 
75
        /**
 
76
         * @return minimum observed value so far
 
77
         * NOTE: exact.
 
78
         */
 
79
        inline Sample min() const { return _min; }
 
80
 
 
81
        /**
 
82
         * @return maximum observed value so far
 
83
         * NOTE: exact.
 
84
         */
 
85
        inline Sample max() const { return _max; }
 
86
 
 
87
        /**
 
88
         * Appends the basic estimators to the provided BSONObjBuilder.
 
89
         */
 
90
        void appendBasicToBSONObjBuilder(BSONObjBuilder& b) const;
 
91
 
 
92
    private:
 
93
        size_t _count;
 
94
        double _sum;
 
95
        double _diff; // sum of squares of differences from the (then-current) mean
 
96
        Sample _min;
 
97
        Sample _max;
 
98
    };
 
99
 
 
100
    /**
 
101
     * Computes 'NumQuantiles' quantiles.
 
102
     *
 
103
     * The quantiles at probability 0 and 1 (minimum and maximum observations) are always computed.
 
104
     * Thus DistributionEstimators<3> computes the the 1st, 2nd and 3rd quartiles (probabilities
 
105
     * .25, .50, .75) and the default 0th and 5th (min and max).
 
106
     *
 
107
     * The quantile estimators are mean square consistent (they become a better approximation of the
 
108
     * actual quantiles as the sample size grows).
 
109
     */
 
110
    template <std::size_t NumQuantiles>
 
111
    class DistributionEstimators {
 
112
    public:
 
113
        DistributionEstimators();
 
114
 
 
115
        DistributionEstimators& operator <<(const double sample);
 
116
 
 
117
        /**
 
118
         * Number of computed quantiles, excluding minimum and maximum.
 
119
         */
 
120
        static const size_t numberOfQuantiles = NumQuantiles;
 
121
 
 
122
        /**
 
123
         * Updates the estimators with another observed value.
 
124
         */
 
125
        inline double quantile(std::size_t i) const {
 
126
            massert(16476, "the requested value is out of the range of the computed quantiles",
 
127
                    i <= NumQuantiles + 1);
 
128
            return this->_heights[2 * i];
 
129
        }
 
130
 
 
131
        /**
 
132
         * @return true when enough value has been observed to output sensible quantiles
 
133
         */
 
134
        inline bool quantilesReady() const {
 
135
            return _count >= NumMarkers;
 
136
        }
 
137
 
 
138
        /**
 
139
         * @return estimated minimum
 
140
         *
 
141
         * NOTE: use SimpleEstimators::min for an exact value.
 
142
         */
 
143
        inline double min() const {
 
144
            return quantile(0);
 
145
        }
 
146
 
 
147
        /**
 
148
         * @return estimated maximum
 
149
         *
 
150
         * NOTE: use SimpleEstimators::max for an exact value.
 
151
         */
 
152
        inline double max() const {
 
153
            return quantile(NumQuantiles + 1);
 
154
        }
 
155
 
 
156
        /**
 
157
         * @return estimated median (2nd quartile)
 
158
         */
 
159
        inline double median() const {
 
160
            return icdf(.5);
 
161
        }
 
162
 
 
163
        /**
 
164
         * @return probability associated with the i-th quantile
 
165
         */
 
166
        inline double probability(std::size_t i) const {
 
167
            return i * 1. / (NumQuantiles + 1);
 
168
        }
 
169
 
 
170
        /**
 
171
         * @return value for the nearest available quantile for probability 'prob'
 
172
         */
 
173
        inline double icdf(double prob) const {
 
174
            int quant = static_cast<int>(prob * (NumQuantiles + 1) + 0.5);
 
175
            return quantile(quant);
 
176
        }
 
177
 
 
178
        /**
 
179
         * Appends the quantiles to the provided BSONArrayBuilder.
 
180
         * REQUIRES e.quantilesReady() == true
 
181
         */
 
182
        void appendQuantilesToBSONArrayBuilder(BSONArrayBuilder& arr) const;
 
183
 
 
184
    private:
 
185
        inline double _positions_increments(std::size_t i) const;
 
186
 
 
187
        int _count;
 
188
        enum { NumMarkers = 2 * NumQuantiles + 3 };
 
189
        double _heights[NumMarkers];              // q_i
 
190
        double _actual_positions[NumMarkers];     // n_i
 
191
        double _desired_positions[NumMarkers];    // d_i
 
192
    };
 
193
 
 
194
    /**
 
195
     * Provides the funcionality of both BasicEstimators and DistributionEstimators.
 
196
     */
 
197
    template <class Sample, std::size_t NumQuantiles>
 
198
    class SummaryEstimators :
 
199
            // Multiple-inheritance
 
200
            public BasicEstimators<Sample>,
 
201
            public DistributionEstimators<NumQuantiles> {
 
202
    public:
 
203
        // Dispatch samples to the inherited estimators
 
204
        inline SummaryEstimators& operator<<(const Sample sample) {
 
205
            this->BasicEstimators<Sample>::operator<<(sample);
 
206
            this->DistributionEstimators<NumQuantiles>::operator<<(sample);
 
207
            return *this;
 
208
        }
 
209
 
 
210
        // Expose the exact values
 
211
        inline Sample min() const {
 
212
            return this->BasicEstimators<Sample>::min();
 
213
        }
 
214
 
 
215
        inline Sample max() const {
 
216
            return this->BasicEstimators<Sample>::max();
 
217
        }
 
218
 
 
219
        /**
 
220
         * @return a summary of the computed estimators as a BSONObj.
 
221
         */
 
222
        BSONObj statisticSummaryToBSONObj() const;
 
223
    };
 
224
 
 
225
} // namespace mongo
 
226
 
 
227
#include "mongo/util/descriptive_stats-inl.h"