]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /////////////////////////////////////////////////////////////////////////////// |
2 | // median.hpp | |
3 | // | |
4 | // Copyright 2006 Eric Niebler, Olivier Gygi. 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) | |
7 | ||
8 | #ifndef BOOST_ACCUMULATORS_STATISTICS_MEDIAN_HPP_EAN_28_10_2005 | |
9 | #define BOOST_ACCUMULATORS_STATISTICS_MEDIAN_HPP_EAN_28_10_2005 | |
10 | ||
11 | #include <boost/mpl/placeholders.hpp> | |
12 | #include <boost/range/iterator_range.hpp> | |
13 | #include <boost/accumulators/framework/accumulator_base.hpp> | |
14 | #include <boost/accumulators/framework/extractor.hpp> | |
15 | #include <boost/accumulators/numeric/functional.hpp> | |
16 | #include <boost/accumulators/framework/parameters/sample.hpp> | |
17 | #include <boost/accumulators/framework/depends_on.hpp> | |
18 | #include <boost/accumulators/statistics_fwd.hpp> | |
19 | #include <boost/accumulators/statistics/count.hpp> | |
20 | #include <boost/accumulators/statistics/p_square_quantile.hpp> | |
21 | #include <boost/accumulators/statistics/density.hpp> | |
22 | #include <boost/accumulators/statistics/p_square_cumul_dist.hpp> | |
23 | ||
24 | namespace boost { namespace accumulators | |
25 | { | |
26 | ||
27 | namespace impl | |
28 | { | |
29 | /////////////////////////////////////////////////////////////////////////////// | |
30 | // median_impl | |
31 | // | |
32 | /** | |
33 | @brief Median estimation based on the \f$P^2\f$ quantile estimator | |
34 | ||
35 | The \f$P^2\f$ algorithm is invoked with a quantile probability of 0.5. | |
36 | */ | |
37 | template<typename Sample> | |
38 | struct median_impl | |
39 | : accumulator_base | |
40 | { | |
41 | // for boost::result_of | |
42 | typedef typename numeric::functional::fdiv<Sample, std::size_t>::result_type result_type; | |
43 | ||
44 | median_impl(dont_care) {} | |
45 | ||
46 | template<typename Args> | |
47 | result_type result(Args const &args) const | |
48 | { | |
49 | return p_square_quantile_for_median(args); | |
50 | } | |
51 | }; | |
52 | /////////////////////////////////////////////////////////////////////////////// | |
53 | // with_density_median_impl | |
54 | // | |
55 | /** | |
56 | @brief Median estimation based on the density estimator | |
57 | ||
58 | The algorithm determines the bin in which the \f$0.5*cnt\f$-th sample lies, \f$cnt\f$ being | |
59 | the total number of samples. It returns the approximate horizontal position of this sample, | |
60 | based on a linear interpolation inside the bin. | |
61 | */ | |
62 | template<typename Sample> | |
63 | struct with_density_median_impl | |
64 | : accumulator_base | |
65 | { | |
66 | typedef typename numeric::functional::fdiv<Sample, std::size_t>::result_type float_type; | |
67 | typedef std::vector<std::pair<float_type, float_type> > histogram_type; | |
68 | typedef iterator_range<typename histogram_type::iterator> range_type; | |
69 | // for boost::result_of | |
70 | typedef float_type result_type; | |
71 | ||
72 | template<typename Args> | |
73 | with_density_median_impl(Args const &args) | |
74 | : sum(numeric::fdiv(args[sample | Sample()], (std::size_t)1)) | |
75 | , is_dirty(true) | |
76 | { | |
77 | } | |
78 | ||
79 | void operator ()(dont_care) | |
80 | { | |
81 | this->is_dirty = true; | |
82 | } | |
83 | ||
84 | ||
85 | template<typename Args> | |
86 | result_type result(Args const &args) const | |
87 | { | |
88 | if (this->is_dirty) | |
89 | { | |
90 | this->is_dirty = false; | |
91 | ||
92 | std::size_t cnt = count(args); | |
93 | range_type histogram = density(args); | |
94 | typename range_type::iterator it = histogram.begin(); | |
95 | while (this->sum < 0.5 * cnt) | |
96 | { | |
97 | this->sum += it->second * cnt; | |
98 | ++it; | |
99 | } | |
100 | --it; | |
101 | float_type over = numeric::fdiv(this->sum - 0.5 * cnt, it->second * cnt); | |
102 | this->median = it->first * over + (it + 1)->first * (1. - over); | |
103 | } | |
104 | ||
105 | return this->median; | |
106 | } | |
107 | ||
108 | private: | |
109 | mutable float_type sum; | |
110 | mutable bool is_dirty; | |
111 | mutable float_type median; | |
112 | }; | |
113 | ||
114 | /////////////////////////////////////////////////////////////////////////////// | |
115 | // with_p_square_cumulative_distribution_median_impl | |
116 | // | |
117 | /** | |
118 | @brief Median estimation based on the \f$P^2\f$ cumulative distribution estimator | |
119 | ||
120 | The algorithm determines the first (leftmost) bin with a height exceeding 0.5. It | |
121 | returns the approximate horizontal position of where the cumulative distribution | |
122 | equals 0.5, based on a linear interpolation inside the bin. | |
123 | */ | |
124 | template<typename Sample> | |
125 | struct with_p_square_cumulative_distribution_median_impl | |
126 | : accumulator_base | |
127 | { | |
128 | typedef typename numeric::functional::fdiv<Sample, std::size_t>::result_type float_type; | |
129 | typedef std::vector<std::pair<float_type, float_type> > histogram_type; | |
130 | typedef iterator_range<typename histogram_type::iterator> range_type; | |
131 | // for boost::result_of | |
132 | typedef float_type result_type; | |
133 | ||
134 | with_p_square_cumulative_distribution_median_impl(dont_care) | |
135 | : is_dirty(true) | |
136 | { | |
137 | } | |
138 | ||
139 | void operator ()(dont_care) | |
140 | { | |
141 | this->is_dirty = true; | |
142 | } | |
143 | ||
144 | template<typename Args> | |
145 | result_type result(Args const &args) const | |
146 | { | |
147 | if (this->is_dirty) | |
148 | { | |
149 | this->is_dirty = false; | |
150 | ||
151 | range_type histogram = p_square_cumulative_distribution(args); | |
152 | typename range_type::iterator it = histogram.begin(); | |
153 | while (it->second < 0.5) | |
154 | { | |
155 | ++it; | |
156 | } | |
157 | float_type over = numeric::fdiv(it->second - 0.5, it->second - (it - 1)->second); | |
158 | this->median = it->first * over + (it + 1)->first * ( 1. - over ); | |
159 | } | |
160 | ||
161 | return this->median; | |
162 | } | |
163 | private: | |
164 | ||
165 | mutable bool is_dirty; | |
166 | mutable float_type median; | |
167 | }; | |
168 | ||
169 | } // namespace impl | |
170 | ||
171 | /////////////////////////////////////////////////////////////////////////////// | |
172 | // tag::median | |
173 | // tag::with_densisty_median | |
174 | // tag::with_p_square_cumulative_distribution_median | |
175 | // | |
176 | namespace tag | |
177 | { | |
178 | struct median | |
179 | : depends_on<p_square_quantile_for_median> | |
180 | { | |
181 | /// INTERNAL ONLY | |
182 | /// | |
183 | typedef accumulators::impl::median_impl<mpl::_1> impl; | |
184 | }; | |
185 | struct with_density_median | |
186 | : depends_on<count, density> | |
187 | { | |
188 | /// INTERNAL ONLY | |
189 | /// | |
190 | typedef accumulators::impl::with_density_median_impl<mpl::_1> impl; | |
191 | }; | |
192 | struct with_p_square_cumulative_distribution_median | |
193 | : depends_on<p_square_cumulative_distribution> | |
194 | { | |
195 | /// INTERNAL ONLY | |
196 | /// | |
197 | typedef accumulators::impl::with_p_square_cumulative_distribution_median_impl<mpl::_1> impl; | |
198 | }; | |
199 | } | |
200 | ||
201 | /////////////////////////////////////////////////////////////////////////////// | |
202 | // extract::median | |
203 | // extract::with_density_median | |
204 | // extract::with_p_square_cumulative_distribution_median | |
205 | // | |
206 | namespace extract | |
207 | { | |
208 | extractor<tag::median> const median = {}; | |
209 | extractor<tag::with_density_median> const with_density_median = {}; | |
210 | extractor<tag::with_p_square_cumulative_distribution_median> const with_p_square_cumulative_distribution_median = {}; | |
211 | ||
212 | BOOST_ACCUMULATORS_IGNORE_GLOBAL(median) | |
213 | BOOST_ACCUMULATORS_IGNORE_GLOBAL(with_density_median) | |
214 | BOOST_ACCUMULATORS_IGNORE_GLOBAL(with_p_square_cumulative_distribution_median) | |
215 | } | |
216 | ||
217 | using extract::median; | |
218 | using extract::with_density_median; | |
219 | using extract::with_p_square_cumulative_distribution_median; | |
220 | ||
221 | // median(with_p_square_quantile) -> median | |
222 | template<> | |
223 | struct as_feature<tag::median(with_p_square_quantile)> | |
224 | { | |
225 | typedef tag::median type; | |
226 | }; | |
227 | ||
228 | // median(with_density) -> with_density_median | |
229 | template<> | |
230 | struct as_feature<tag::median(with_density)> | |
231 | { | |
232 | typedef tag::with_density_median type; | |
233 | }; | |
234 | ||
235 | // median(with_p_square_cumulative_distribution) -> with_p_square_cumulative_distribution_median | |
236 | template<> | |
237 | struct as_feature<tag::median(with_p_square_cumulative_distribution)> | |
238 | { | |
239 | typedef tag::with_p_square_cumulative_distribution_median type; | |
240 | }; | |
241 | ||
242 | // for the purposes of feature-based dependency resolution, | |
243 | // with_density_median and with_p_square_cumulative_distribution_median | |
244 | // provide the same feature as median | |
245 | template<> | |
246 | struct feature_of<tag::with_density_median> | |
247 | : feature_of<tag::median> | |
248 | { | |
249 | }; | |
250 | ||
251 | template<> | |
252 | struct feature_of<tag::with_p_square_cumulative_distribution_median> | |
253 | : feature_of<tag::median> | |
254 | { | |
255 | }; | |
256 | ||
257 | // So that median can be automatically substituted with | |
258 | // weighted_median when the weight parameter is non-void. | |
259 | template<> | |
260 | struct as_weighted_feature<tag::median> | |
261 | { | |
262 | typedef tag::weighted_median type; | |
263 | }; | |
264 | ||
265 | template<> | |
266 | struct feature_of<tag::weighted_median> | |
267 | : feature_of<tag::median> | |
268 | { | |
269 | }; | |
270 | ||
271 | // So that with_density_median can be automatically substituted with | |
272 | // with_density_weighted_median when the weight parameter is non-void. | |
273 | template<> | |
274 | struct as_weighted_feature<tag::with_density_median> | |
275 | { | |
276 | typedef tag::with_density_weighted_median type; | |
277 | }; | |
278 | ||
279 | template<> | |
280 | struct feature_of<tag::with_density_weighted_median> | |
281 | : feature_of<tag::with_density_median> | |
282 | { | |
283 | }; | |
284 | ||
285 | // So that with_p_square_cumulative_distribution_median can be automatically substituted with | |
286 | // with_p_square_cumulative_distribution_weighted_median when the weight parameter is non-void. | |
287 | template<> | |
288 | struct as_weighted_feature<tag::with_p_square_cumulative_distribution_median> | |
289 | { | |
290 | typedef tag::with_p_square_cumulative_distribution_weighted_median type; | |
291 | }; | |
292 | ||
293 | template<> | |
294 | struct feature_of<tag::with_p_square_cumulative_distribution_weighted_median> | |
295 | : feature_of<tag::with_p_square_cumulative_distribution_median> | |
296 | { | |
297 | }; | |
298 | ||
299 | }} // namespace boost::accumulators | |
300 | ||
301 | #endif |