/usr/include/boost/accumulators/statistics/extended_p_square.hpp is in libboost1.55-dev 1.55.0+dfsg-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 | ///////////////////////////////////////////////////////////////////////////////
// extended_p_square.hpp
//
// Copyright 2005 Daniel Egloff. Distributed under the Boost
// Software License, Version 1.0. (See accompanying file
// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
#ifndef BOOST_ACCUMULATORS_STATISTICS_EXTENDED_SINGLE_HPP_DE_01_01_2006
#define BOOST_ACCUMULATORS_STATISTICS_EXTENDED_SINGLE_HPP_DE_01_01_2006
#include <vector>
#include <functional>
#include <boost/range/begin.hpp>
#include <boost/range/end.hpp>
#include <boost/range/iterator_range.hpp>
#include <boost/iterator/transform_iterator.hpp>
#include <boost/iterator/counting_iterator.hpp>
#include <boost/iterator/permutation_iterator.hpp>
#include <boost/parameter/keyword.hpp>
#include <boost/mpl/placeholders.hpp>
#include <boost/accumulators/accumulators_fwd.hpp>
#include <boost/accumulators/framework/extractor.hpp>
#include <boost/accumulators/numeric/functional.hpp>
#include <boost/accumulators/framework/parameters/sample.hpp>
#include <boost/accumulators/framework/depends_on.hpp>
#include <boost/accumulators/statistics_fwd.hpp>
#include <boost/accumulators/statistics/count.hpp>
#include <boost/accumulators/statistics/times2_iterator.hpp>
namespace boost { namespace accumulators
{
///////////////////////////////////////////////////////////////////////////////
// probabilities named parameter
//
BOOST_PARAMETER_NESTED_KEYWORD(tag, extended_p_square_probabilities, probabilities)
BOOST_ACCUMULATORS_IGNORE_GLOBAL(extended_p_square_probabilities)
namespace impl
{
///////////////////////////////////////////////////////////////////////////////
// extended_p_square_impl
// multiple quantile estimation
/**
@brief Multiple quantile estimation with the extended \f$P^2\f$ algorithm
Extended \f$P^2\f$ algorithm for estimation of several quantiles without storing samples.
Assume that \f$m\f$ quantiles \f$\xi_{p_1}, \ldots, \xi_{p_m}\f$ are to be estimated.
Instead of storing the whole sample cumulative distribution, the algorithm maintains only
\f$m+2\f$ principal markers and \f$m+1\f$ middle markers, whose positions are updated
with each sample and whose heights are adjusted (if necessary) using a piecewise-parablic
formula. The heights of these central markers are the current estimates of the quantiles
and returned as an iterator range.
For further details, see
K. E. E. Raatikainen, Simultaneous estimation of several quantiles, Simulation, Volume 49,
Number 4 (October), 1986, p. 159-164.
The extended \f$ P^2 \f$ algorithm generalizes the \f$ P^2 \f$ algorithm of
R. Jain and I. Chlamtac, The P^2 algorithm for dynamic calculation of quantiles and
histograms without storing observations, Communications of the ACM,
Volume 28 (October), Number 10, 1985, p. 1076-1085.
@param extended_p_square_probabilities A vector of quantile probabilities.
*/
template<typename Sample>
struct extended_p_square_impl
: accumulator_base
{
typedef typename numeric::functional::fdiv<Sample, std::size_t>::result_type float_type;
typedef std::vector<float_type> array_type;
// for boost::result_of
typedef iterator_range<
detail::lvalue_index_iterator<
permutation_iterator<
typename array_type::const_iterator
, detail::times2_iterator
>
>
> result_type;
template<typename Args>
extended_p_square_impl(Args const &args)
: probabilities(
boost::begin(args[extended_p_square_probabilities])
, boost::end(args[extended_p_square_probabilities])
)
, heights(2 * probabilities.size() + 3)
, actual_positions(heights.size())
, desired_positions(heights.size())
, positions_increments(heights.size())
{
std::size_t num_quantiles = this->probabilities.size();
std::size_t num_markers = this->heights.size();
for(std::size_t i = 0; i < num_markers; ++i)
{
this->actual_positions[i] = i + 1;
}
this->positions_increments[0] = 0.;
this->positions_increments[num_markers - 1] = 1.;
for(std::size_t i = 0; i < num_quantiles; ++i)
{
this->positions_increments[2 * i + 2] = probabilities[i];
}
for(std::size_t i = 0; i <= num_quantiles; ++i)
{
this->positions_increments[2 * i + 1] =
0.5 * (this->positions_increments[2 * i] + this->positions_increments[2 * i + 2]);
}
for(std::size_t i = 0; i < num_markers; ++i)
{
this->desired_positions[i] = 1. + 2. * (num_quantiles + 1.) * this->positions_increments[i];
}
}
template<typename Args>
void operator ()(Args const &args)
{
std::size_t cnt = count(args);
// m+2 principal markers and m+1 middle markers
std::size_t num_markers = 2 * this->probabilities.size() + 3;
// first accumulate num_markers samples
if(cnt <= num_markers)
{
this->heights[cnt - 1] = args[sample];
// complete the initialization of heights by sorting
if(cnt == num_markers)
{
std::sort(this->heights.begin(), this->heights.end());
}
}
else
{
std::size_t sample_cell = 1;
// find cell k = sample_cell such that heights[k-1] <= sample < heights[k]
if(args[sample] < this->heights[0])
{
this->heights[0] = args[sample];
sample_cell = 1;
}
else if(args[sample] >= this->heights[num_markers - 1])
{
this->heights[num_markers - 1] = args[sample];
sample_cell = num_markers - 1;
}
else
{
typedef typename array_type::iterator iterator;
iterator it = std::upper_bound(
this->heights.begin()
, this->heights.end()
, args[sample]
);
sample_cell = std::distance(this->heights.begin(), it);
}
// update actual positions of all markers above sample_cell index
for(std::size_t i = sample_cell; i < num_markers; ++i)
{
++this->actual_positions[i];
}
// update desired positions of all markers
for(std::size_t i = 0; i < num_markers; ++i)
{
this->desired_positions[i] += this->positions_increments[i];
}
// adjust heights and actual positions of markers 1 to num_markers-2 if necessary
for(std::size_t i = 1; i <= num_markers - 2; ++i)
{
// offset to desired position
float_type d = this->desired_positions[i] - this->actual_positions[i];
// offset to next position
float_type dp = this->actual_positions[i+1] - this->actual_positions[i];
// offset to previous position
float_type dm = this->actual_positions[i-1] - this->actual_positions[i];
// height ds
float_type hp = (this->heights[i+1] - this->heights[i]) / dp;
float_type hm = (this->heights[i-1] - this->heights[i]) / dm;
if((d >= 1 && dp > 1) || (d <= -1 && dm < -1))
{
short sign_d = static_cast<short>(d / std::abs(d));
float_type h = this->heights[i] + sign_d / (dp - dm) * ((sign_d - dm)*hp
+ (dp - sign_d) * hm);
// try adjusting heights[i] using p-squared formula
if(this->heights[i - 1] < h && h < this->heights[i + 1])
{
this->heights[i] = h;
}
else
{
// use linear formula
if(d > 0)
{
this->heights[i] += hp;
}
if(d < 0)
{
this->heights[i] -= hm;
}
}
this->actual_positions[i] += sign_d;
}
}
}
}
result_type result(dont_care) const
{
// for i in [1,probabilities.size()], return heights[i * 2]
detail::times2_iterator idx_begin = detail::make_times2_iterator(1);
detail::times2_iterator idx_end = detail::make_times2_iterator(this->probabilities.size() + 1);
return result_type(
make_permutation_iterator(this->heights.begin(), idx_begin)
, make_permutation_iterator(this->heights.begin(), idx_end)
);
}
private:
array_type probabilities; // the quantile probabilities
array_type heights; // q_i
array_type actual_positions; // n_i
array_type desired_positions; // d_i
array_type positions_increments; // f_i
};
} // namespace impl
///////////////////////////////////////////////////////////////////////////////
// tag::extended_p_square
//
namespace tag
{
struct extended_p_square
: depends_on<count>
, extended_p_square_probabilities
{
typedef accumulators::impl::extended_p_square_impl<mpl::_1> impl;
#ifdef BOOST_ACCUMULATORS_DOXYGEN_INVOKED
/// tag::extended_p_square::probabilities named parameter
static boost::parameter::keyword<tag::probabilities> const probabilities;
#endif
};
}
///////////////////////////////////////////////////////////////////////////////
// extract::extended_p_square
//
namespace extract
{
extractor<tag::extended_p_square> const extended_p_square = {};
BOOST_ACCUMULATORS_IGNORE_GLOBAL(extended_p_square)
}
using extract::extended_p_square;
// So that extended_p_square can be automatically substituted with
// weighted_extended_p_square when the weight parameter is non-void
template<>
struct as_weighted_feature<tag::extended_p_square>
{
typedef tag::weighted_extended_p_square type;
};
template<>
struct feature_of<tag::weighted_extended_p_square>
: feature_of<tag::extended_p_square>
{
};
}} // namespace boost::accumulators
#endif
|