| |
| /////////////////////////////////////////////////////////////////////////////// |
| // density.hpp |
| // |
| // Copyright 2006 Daniel Egloff, Olivier Gygi. 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_DENSITY_HPP_DE_01_01_2006 |
| #define BOOST_ACCUMULATORS_STATISTICS_DENSITY_HPP_DE_01_01_2006 |
| |
| #include <vector> |
| #include <limits> |
| #include <functional> |
| #include <boost/range.hpp> |
| #include <boost/parameter/keyword.hpp> |
| #include <boost/mpl/placeholders.hpp> |
| #include <boost/accumulators/framework/accumulator_base.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/max.hpp> |
| #include <boost/accumulators/statistics/min.hpp> |
| |
| namespace boost { namespace accumulators |
| { |
| |
| /////////////////////////////////////////////////////////////////////////////// |
| // cache_size and num_bins named parameters |
| // |
| BOOST_PARAMETER_NESTED_KEYWORD(tag, density_cache_size, cache_size) |
| BOOST_PARAMETER_NESTED_KEYWORD(tag, density_num_bins, num_bins) |
| |
| namespace impl |
| { |
| /////////////////////////////////////////////////////////////////////////////// |
| // density_impl |
| // density histogram |
| /** |
| @brief Histogram density estimator |
| |
| The histogram density estimator returns a histogram of the sample distribution. The positions and sizes of the bins |
| are determined using a specifiable number of cached samples (cache_size). The range between the minimum and the |
| maximum of the cached samples is subdivided into a specifiable number of bins (num_bins) of same size. Additionally, |
| an under- and an overflow bin is added to capture future under- and overflow samples. Once the bins are determined, |
| the cached samples and all subsequent samples are added to the correct bins. At the end, a range of std::pair is |
| return, where each pair contains the position of the bin (lower bound) and the samples count (normalized with the |
| total number of samples). |
| |
| @param density_cache_size Number of first samples used to determine min and max. |
| @param density_num_bins Number of bins (two additional bins collect under- and overflow samples). |
| */ |
| template<typename Sample> |
| struct density_impl |
| : accumulator_base |
| { |
| typedef typename numeric::functional::average<Sample, std::size_t>::result_type float_type; |
| typedef std::vector<std::pair<float_type, float_type> > histogram_type; |
| typedef std::vector<float_type> array_type; |
| // for boost::result_of |
| typedef iterator_range<typename histogram_type::iterator> result_type; |
| |
| template<typename Args> |
| density_impl(Args const &args) |
| : cache_size(args[density_cache_size]) |
| , cache(cache_size) |
| , num_bins(args[density_num_bins]) |
| , samples_in_bin(num_bins + 2, 0.) |
| , bin_positions(num_bins + 2) |
| , histogram( |
| num_bins + 2 |
| , std::make_pair( |
| numeric::average(args[sample | Sample()],(std::size_t)1) |
| , numeric::average(args[sample | Sample()],(std::size_t)1) |
| ) |
| ) |
| , is_dirty(true) |
| { |
| } |
| |
| template<typename Args> |
| void operator ()(Args const &args) |
| { |
| this->is_dirty = true; |
| |
| std::size_t cnt = count(args); |
| |
| // Fill up cache with cache_size first samples |
| if (cnt <= this->cache_size) |
| { |
| this->cache[cnt - 1] = args[sample]; |
| } |
| |
| // Once cache_size samples have been accumulated, create num_bins bins of same size between |
| // the minimum and maximum of the cached samples as well as an under- and and an overflow bin. |
| // Store their lower bounds (bin_positions) and fill the bins with the cached samples (samples_in_bin). |
| if (cnt == this->cache_size) |
| { |
| float_type minimum = numeric::average((min)(args), (std::size_t)1); |
| float_type maximum = numeric::average((max)(args), (std::size_t)1); |
| float_type bin_size = numeric::average(maximum - minimum, this->num_bins ); |
| |
| // determine bin positions (their lower bounds) |
| for (std::size_t i = 0; i < this->num_bins + 2; ++i) |
| { |
| this->bin_positions[i] = minimum + (i - 1.) * bin_size; |
| } |
| |
| for (typename array_type::const_iterator iter = this->cache.begin(); iter != this->cache.end(); ++iter) |
| { |
| if (*iter < this->bin_positions[1]) |
| { |
| ++(this->samples_in_bin[0]); |
| } |
| else if (*iter >= this->bin_positions[this->num_bins + 1]) |
| { |
| ++(this->samples_in_bin[this->num_bins + 1]); |
| } |
| else |
| { |
| typename array_type::iterator it = std::upper_bound( |
| this->bin_positions.begin() |
| , this->bin_positions.end() |
| , *iter |
| ); |
| |
| std::size_t d = std::distance(this->bin_positions.begin(), it); |
| ++(this->samples_in_bin[d - 1]); |
| } |
| } |
| } |
| // Add each subsequent sample to the correct bin |
| else if (cnt > this->cache_size) |
| { |
| if (args[sample] < this->bin_positions[1]) |
| { |
| ++(this->samples_in_bin[0]); |
| } |
| else if (args[sample] >= this->bin_positions[this->num_bins + 1]) |
| { |
| ++(this->samples_in_bin[this->num_bins + 1]); |
| } |
| else |
| { |
| typename array_type::iterator it = std::upper_bound( |
| this->bin_positions.begin() |
| , this->bin_positions.end() |
| , args[sample] |
| ); |
| |
| std::size_t d = std::distance(this->bin_positions.begin(), it); |
| ++(this->samples_in_bin[d - 1]); |
| } |
| } |
| } |
| |
| /** |
| @pre The number of samples must meet or exceed the cache size |
| */ |
| template<typename Args> |
| result_type result(Args const &args) const |
| { |
| if (this->is_dirty) |
| { |
| this->is_dirty = false; |
| |
| // creates a vector of std::pair where each pair i holds |
| // the values bin_positions[i] (x-axis of histogram) and |
| // samples_in_bin[i] / cnt (y-axis of histogram). |
| |
| for (std::size_t i = 0; i < this->num_bins + 2; ++i) |
| { |
| this->histogram[i] = std::make_pair(this->bin_positions[i], numeric::average(this->samples_in_bin[i], count(args))); |
| } |
| } |
| // returns a range of pairs |
| return make_iterator_range(this->histogram); |
| } |
| |
| private: |
| std::size_t cache_size; // number of cached samples |
| array_type cache; // cache to store the first cache_size samples |
| std::size_t num_bins; // number of bins |
| array_type samples_in_bin; // number of samples in each bin |
| array_type bin_positions; // lower bounds of bins |
| mutable histogram_type histogram; // histogram |
| mutable bool is_dirty; |
| }; |
| |
| } // namespace impl |
| |
| /////////////////////////////////////////////////////////////////////////////// |
| // tag::density |
| // |
| namespace tag |
| { |
| struct density |
| : depends_on<count, min, max> |
| , density_cache_size |
| , density_num_bins |
| { |
| /// INTERNAL ONLY |
| /// |
| typedef accumulators::impl::density_impl<mpl::_1> impl; |
| |
| #ifdef BOOST_ACCUMULATORS_DOXYGEN_INVOKED |
| /// tag::density::cache_size named parameter |
| /// tag::density::num_bins named parameter |
| static boost::parameter::keyword<density_cache_size> const cache_size; |
| static boost::parameter::keyword<density_num_bins> const num_bins; |
| #endif |
| }; |
| } |
| |
| /////////////////////////////////////////////////////////////////////////////// |
| // extract::density |
| // |
| namespace extract |
| { |
| extractor<tag::density> const density = {}; |
| |
| BOOST_ACCUMULATORS_IGNORE_GLOBAL(density) |
| } |
| |
| using extract::density; |
| |
| // So that density can be automatically substituted |
| // with weighted_density when the weight parameter is non-void. |
| template<> |
| struct as_weighted_feature<tag::density> |
| { |
| typedef tag::weighted_density type; |
| }; |
| |
| template<> |
| struct feature_of<tag::weighted_density> |
| : feature_of<tag::density> |
| { |
| }; |
| |
| }} // namespace boost::accumulators |
| |
| #endif |