1 ///////////////////////////////////////////////////////////////////////////////
2 // weighted_p_square_quantile.hpp
4 // Copyright 2005 Daniel Egloff. Distributed under the Boost
5 // Software License, Version 1.0. (See accompanying file
6 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
8 #ifndef BOOST_ACCUMULATORS_STATISTICS_WEIGHTED_P_SQUARE_QUANTILE_HPP_DE_01_01_2006
9 #define BOOST_ACCUMULATORS_STATISTICS_WEIGHTED_P_SQUARE_QUANTILE_HPP_DE_01_01_2006
13 #include <boost/array.hpp>
14 #include <boost/parameter/keyword.hpp>
15 #include <boost/mpl/placeholders.hpp>
16 #include <boost/type_traits/is_same.hpp>
17 #include <boost/accumulators/framework/accumulator_base.hpp>
18 #include <boost/accumulators/framework/extractor.hpp>
19 #include <boost/accumulators/numeric/functional.hpp>
20 #include <boost/accumulators/framework/parameters/sample.hpp>
21 #include <boost/accumulators/statistics_fwd.hpp>
22 #include <boost/accumulators/statistics/count.hpp>
23 #include <boost/accumulators/statistics/sum.hpp>
24 #include <boost/accumulators/statistics/parameters/quantile_probability.hpp>
26 namespace boost { namespace accumulators
30 ///////////////////////////////////////////////////////////////////////////////
31 // weighted_p_square_quantile_impl
32 // single quantile estimation with weighted samples
34 @brief Single quantile estimation with the \f$P^2\f$ algorithm for weighted samples
36 This version of the \f$P^2\f$ algorithm extends the \f$P^2\f$ algorithm to support weighted samples.
37 The \f$P^2\f$ algorithm estimates a quantile dynamically without storing samples. Instead of
38 storing the whole sample cumulative distribution, only five points (markers) are stored. The heights
39 of these markers are the minimum and the maximum of the samples and the current estimates of the
40 \f$(p/2)\f$-, \f$p\f$ - and \f$(1+p)/2\f$ -quantiles. Their positions are equal to the number
41 of samples that are smaller or equal to the markers. Each time a new sample is added, the
42 positions of the markers are updated and if necessary their heights are adjusted using a piecewise-
45 For further details, see
47 R. Jain and I. Chlamtac, The P^2 algorithmus for dynamic calculation of quantiles and
48 histograms without storing observations, Communications of the ACM,
49 Volume 28 (October), Number 10, 1985, p. 1076-1085.
51 @param quantile_probability
53 template<typename Sample, typename Weight, typename Impl>
54 struct weighted_p_square_quantile_impl
57 typedef typename numeric::functional::multiplies<Sample, Weight>::result_type weighted_sample;
58 typedef typename numeric::functional::average<weighted_sample, std::size_t>::result_type float_type;
59 typedef array<float_type, 5> array_type;
60 // for boost::result_of
61 typedef float_type result_type;
63 template<typename Args>
64 weighted_p_square_quantile_impl(Args const &args)
65 : p(is_same<Impl, for_median>::value ? 0.5 : args[quantile_probability | 0.5])
72 template<typename Args>
73 void operator ()(Args const &args)
75 std::size_t cnt = count(args);
77 // accumulate 5 first samples
80 this->heights[cnt - 1] = args[sample];
82 // In this initialization phase, actual_positions stores the weights of the
83 // inital samples that are needed at the end of the initialization phase to
84 // compute the correct initial positions of the markers.
85 this->actual_positions[cnt - 1] = args[weight];
87 // complete the initialization of heights and actual_positions by sorting
90 // TODO: we need to sort the initial samples (in heights) in ascending order and
91 // sort their weights (in actual_positions) the same way. The following lines do
92 // it, but there must be a better and more efficient way of doing this.
93 typename array_type::iterator it_begin, it_end, it_min;
95 it_begin = this->heights.begin();
96 it_end = this->heights.end();
100 while (it_begin != it_end)
102 it_min = std::min_element(it_begin, it_end);
103 std::size_t d = std::distance(it_begin, it_min);
104 std::swap(*it_begin, *it_min);
105 std::swap(this->actual_positions[pos], this->actual_positions[pos + d]);
110 // calculate correct initial actual positions
111 for (std::size_t i = 1; i < 5; ++i)
113 this->actual_positions[i] += this->actual_positions[i - 1];
119 std::size_t sample_cell = 1; // k
121 // find cell k such that heights[k-1] <= args[sample] < heights[k] and adjust extreme values
122 if (args[sample] < this->heights[0])
124 this->heights[0] = args[sample];
125 this->actual_positions[0] = args[weight];
128 else if (this->heights[4] <= args[sample])
130 this->heights[4] = args[sample];
135 typedef typename array_type::iterator iterator;
136 iterator it = std::upper_bound(
137 this->heights.begin()
138 , this->heights.end()
142 sample_cell = std::distance(this->heights.begin(), it);
145 // increment positions of markers above sample_cell
146 for (std::size_t i = sample_cell; i < 5; ++i)
148 this->actual_positions[i] += args[weight];
151 // update desired positions for all markers
152 this->desired_positions[0] = this->actual_positions[0];
153 this->desired_positions[1] = (sum_of_weights(args) - this->actual_positions[0])
154 * this->p/2. + this->actual_positions[0];
155 this->desired_positions[2] = (sum_of_weights(args) - this->actual_positions[0])
156 * this->p + this->actual_positions[0];
157 this->desired_positions[3] = (sum_of_weights(args) - this->actual_positions[0])
158 * (1. + this->p)/2. + this->actual_positions[0];
159 this->desired_positions[4] = sum_of_weights(args);
161 // adjust height and actual positions of markers 1 to 3 if necessary
162 for (std::size_t i = 1; i <= 3; ++i)
164 // offset to desired positions
165 float_type d = this->desired_positions[i] - this->actual_positions[i];
167 // offset to next position
168 float_type dp = this->actual_positions[i + 1] - this->actual_positions[i];
170 // offset to previous position
171 float_type dm = this->actual_positions[i - 1] - this->actual_positions[i];
174 float_type hp = (this->heights[i + 1] - this->heights[i]) / dp;
175 float_type hm = (this->heights[i - 1] - this->heights[i]) / dm;
177 if ( ( d >= 1. && dp > 1. ) || ( d <= -1. && dm < -1. ) )
179 short sign_d = static_cast<short>(d / std::abs(d));
181 // try adjusting heights[i] using p-squared formula
182 float_type h = this->heights[i] + sign_d / (dp - dm) * ( (sign_d - dm) * hp + (dp - sign_d) * hm );
184 if ( this->heights[i - 1] < h && h < this->heights[i + 1] )
186 this->heights[i] = h;
190 // use linear formula
193 this->heights[i] += hp;
197 this->heights[i] -= hm;
200 this->actual_positions[i] += sign_d;
206 result_type result(dont_care) const
208 return this->heights[2];
212 float_type p; // the quantile probability p
213 array_type heights; // q_i
214 array_type actual_positions; // n_i
215 array_type desired_positions; // n'_i
220 ///////////////////////////////////////////////////////////////////////////////
221 // tag::weighted_p_square_quantile
225 struct weighted_p_square_quantile
226 : depends_on<count, sum_of_weights>
228 typedef accumulators::impl::weighted_p_square_quantile_impl<mpl::_1, mpl::_2, regular> impl;
230 struct weighted_p_square_quantile_for_median
231 : depends_on<count, sum_of_weights>
233 typedef accumulators::impl::weighted_p_square_quantile_impl<mpl::_1, mpl::_2, for_median> impl;
237 ///////////////////////////////////////////////////////////////////////////////
238 // extract::weighted_p_square_quantile
239 // extract::weighted_p_square_quantile_for_median
243 extractor<tag::weighted_p_square_quantile> const weighted_p_square_quantile = {};
244 extractor<tag::weighted_p_square_quantile_for_median> const weighted_p_square_quantile_for_median = {};
246 BOOST_ACCUMULATORS_IGNORE_GLOBAL(weighted_p_square_quantile)
247 BOOST_ACCUMULATORS_IGNORE_GLOBAL(weighted_p_square_quantile_for_median)
250 using extract::weighted_p_square_quantile;
251 using extract::weighted_p_square_quantile_for_median;
253 }} // namespace boost::accumulators