Statistics
| Revision:

root / tmp / org.txm.statsengine.r.core.win32 / res / win32 / library / BH / include / boost / accumulators / statistics / density.hpp @ 2486

History | View | Annotate | Download (9.3 kB)

1 2486 sjacqu01
2 2486 sjacqu01
///////////////////////////////////////////////////////////////////////////////
3 2486 sjacqu01
// density.hpp
4 2486 sjacqu01
//
5 2486 sjacqu01
//  Copyright 2006 Daniel Egloff, Olivier Gygi. Distributed under the Boost
6 2486 sjacqu01
//  Software License, Version 1.0. (See accompanying file
7 2486 sjacqu01
//  LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
8 2486 sjacqu01
9 2486 sjacqu01
#ifndef BOOST_ACCUMULATORS_STATISTICS_DENSITY_HPP_DE_01_01_2006
10 2486 sjacqu01
#define BOOST_ACCUMULATORS_STATISTICS_DENSITY_HPP_DE_01_01_2006
11 2486 sjacqu01
12 2486 sjacqu01
#include <vector>
13 2486 sjacqu01
#include <limits>
14 2486 sjacqu01
#include <functional>
15 2486 sjacqu01
#include <boost/range.hpp>
16 2486 sjacqu01
#include <boost/parameter/keyword.hpp>
17 2486 sjacqu01
#include <boost/mpl/placeholders.hpp>
18 2486 sjacqu01
#include <boost/accumulators/accumulators_fwd.hpp>
19 2486 sjacqu01
#include <boost/accumulators/framework/accumulator_base.hpp>
20 2486 sjacqu01
#include <boost/accumulators/framework/extractor.hpp>
21 2486 sjacqu01
#include <boost/accumulators/numeric/functional.hpp>
22 2486 sjacqu01
#include <boost/accumulators/framework/parameters/sample.hpp>
23 2486 sjacqu01
#include <boost/accumulators/framework/depends_on.hpp>
24 2486 sjacqu01
#include <boost/accumulators/statistics_fwd.hpp>
25 2486 sjacqu01
#include <boost/accumulators/statistics/count.hpp>
26 2486 sjacqu01
#include <boost/accumulators/statistics/max.hpp>
27 2486 sjacqu01
#include <boost/accumulators/statistics/min.hpp>
28 2486 sjacqu01
29 2486 sjacqu01
namespace boost { namespace accumulators
30 2486 sjacqu01
{
31 2486 sjacqu01
32 2486 sjacqu01
///////////////////////////////////////////////////////////////////////////////
33 2486 sjacqu01
// cache_size and num_bins named parameters
34 2486 sjacqu01
//
35 2486 sjacqu01
BOOST_PARAMETER_NESTED_KEYWORD(tag, density_cache_size, cache_size)
36 2486 sjacqu01
BOOST_PARAMETER_NESTED_KEYWORD(tag, density_num_bins, num_bins)
37 2486 sjacqu01
38 2486 sjacqu01
BOOST_ACCUMULATORS_IGNORE_GLOBAL(density_cache_size)
39 2486 sjacqu01
BOOST_ACCUMULATORS_IGNORE_GLOBAL(density_num_bins)
40 2486 sjacqu01
41 2486 sjacqu01
namespace impl
42 2486 sjacqu01
{
43 2486 sjacqu01
    ///////////////////////////////////////////////////////////////////////////////
44 2486 sjacqu01
    // density_impl
45 2486 sjacqu01
    //  density histogram
46 2486 sjacqu01
    /**
47 2486 sjacqu01
        @brief Histogram density estimator
48 2486 sjacqu01

49 2486 sjacqu01
        The histogram density estimator returns a histogram of the sample distribution. The positions and sizes of the bins
50 2486 sjacqu01
        are determined using a specifiable number of cached samples (cache_size). The range between the minimum and the
51 2486 sjacqu01
        maximum of the cached samples is subdivided into a specifiable number of bins (num_bins) of same size. Additionally,
52 2486 sjacqu01
        an under- and an overflow bin is added to capture future under- and overflow samples. Once the bins are determined,
53 2486 sjacqu01
        the cached samples and all subsequent samples are added to the correct bins. At the end, a range of std::pair is
54 2486 sjacqu01
        return, where each pair contains the position of the bin (lower bound) and the samples count (normalized with the
55 2486 sjacqu01
        total number of samples).
56 2486 sjacqu01

57 2486 sjacqu01
        @param  density_cache_size Number of first samples used to determine min and max.
58 2486 sjacqu01
        @param  density_num_bins Number of bins (two additional bins collect under- and overflow samples).
59 2486 sjacqu01
    */
60 2486 sjacqu01
    template<typename Sample>
61 2486 sjacqu01
    struct density_impl
62 2486 sjacqu01
      : accumulator_base
63 2486 sjacqu01
    {
64 2486 sjacqu01
        typedef typename numeric::functional::fdiv<Sample, std::size_t>::result_type float_type;
65 2486 sjacqu01
        typedef std::vector<std::pair<float_type, float_type> > histogram_type;
66 2486 sjacqu01
        typedef std::vector<float_type> array_type;
67 2486 sjacqu01
        // for boost::result_of
68 2486 sjacqu01
        typedef iterator_range<typename histogram_type::iterator> result_type;
69 2486 sjacqu01
70 2486 sjacqu01
        template<typename Args>
71 2486 sjacqu01
        density_impl(Args const &args)
72 2486 sjacqu01
            : cache_size(args[density_cache_size])
73 2486 sjacqu01
            , cache(cache_size)
74 2486 sjacqu01
            , num_bins(args[density_num_bins])
75 2486 sjacqu01
            , samples_in_bin(num_bins + 2, 0.)
76 2486 sjacqu01
            , bin_positions(num_bins + 2)
77 2486 sjacqu01
            , histogram(
78 2486 sjacqu01
                num_bins + 2
79 2486 sjacqu01
              , std::make_pair(
80 2486 sjacqu01
                    numeric::fdiv(args[sample | Sample()],(std::size_t)1)
81 2486 sjacqu01
                  , numeric::fdiv(args[sample | Sample()],(std::size_t)1)
82 2486 sjacqu01
                )
83 2486 sjacqu01
              )
84 2486 sjacqu01
            , is_dirty(true)
85 2486 sjacqu01
        {
86 2486 sjacqu01
        }
87 2486 sjacqu01
88 2486 sjacqu01
        template<typename Args>
89 2486 sjacqu01
        void operator ()(Args const &args)
90 2486 sjacqu01
        {
91 2486 sjacqu01
            this->is_dirty = true;
92 2486 sjacqu01
93 2486 sjacqu01
            std::size_t cnt = count(args);
94 2486 sjacqu01
95 2486 sjacqu01
            // Fill up cache with cache_size first samples
96 2486 sjacqu01
            if (cnt <= this->cache_size)
97 2486 sjacqu01
            {
98 2486 sjacqu01
                this->cache[cnt - 1] = args[sample];
99 2486 sjacqu01
            }
100 2486 sjacqu01
101 2486 sjacqu01
            // Once cache_size samples have been accumulated, create num_bins bins of same size between
102 2486 sjacqu01
            // the minimum and maximum of the cached samples as well as under and overflow bins.
103 2486 sjacqu01
            // Store their lower bounds (bin_positions) and fill the bins with the cached samples (samples_in_bin).
104 2486 sjacqu01
            if (cnt == this->cache_size)
105 2486 sjacqu01
            {
106 2486 sjacqu01
                float_type minimum = numeric::fdiv((min)(args), (std::size_t)1);
107 2486 sjacqu01
                float_type maximum = numeric::fdiv((max)(args), (std::size_t)1);
108 2486 sjacqu01
                float_type bin_size = numeric::fdiv(maximum - minimum, this->num_bins );
109 2486 sjacqu01
110 2486 sjacqu01
                // determine bin positions (their lower bounds)
111 2486 sjacqu01
                for (std::size_t i = 0; i < this->num_bins + 2; ++i)
112 2486 sjacqu01
                {
113 2486 sjacqu01
                    this->bin_positions[i] = minimum + (i - 1.) * bin_size;
114 2486 sjacqu01
                }
115 2486 sjacqu01
116 2486 sjacqu01
                for (typename array_type::const_iterator iter = this->cache.begin(); iter != this->cache.end(); ++iter)
117 2486 sjacqu01
                {
118 2486 sjacqu01
                    if (*iter < this->bin_positions[1])
119 2486 sjacqu01
                    {
120 2486 sjacqu01
                        ++(this->samples_in_bin[0]);
121 2486 sjacqu01
                    }
122 2486 sjacqu01
                    else if (*iter >= this->bin_positions[this->num_bins + 1])
123 2486 sjacqu01
                    {
124 2486 sjacqu01
                        ++(this->samples_in_bin[this->num_bins + 1]);
125 2486 sjacqu01
                    }
126 2486 sjacqu01
                    else
127 2486 sjacqu01
                    {
128 2486 sjacqu01
                        typename array_type::iterator it = std::upper_bound(
129 2486 sjacqu01
                            this->bin_positions.begin()
130 2486 sjacqu01
                          , this->bin_positions.end()
131 2486 sjacqu01
                          , *iter
132 2486 sjacqu01
                        );
133 2486 sjacqu01
134 2486 sjacqu01
                        std::size_t d = std::distance(this->bin_positions.begin(), it);
135 2486 sjacqu01
                        ++(this->samples_in_bin[d - 1]);
136 2486 sjacqu01
                    }
137 2486 sjacqu01
                }
138 2486 sjacqu01
            }
139 2486 sjacqu01
            // Add each subsequent sample to the correct bin
140 2486 sjacqu01
            else if (cnt > this->cache_size)
141 2486 sjacqu01
            {
142 2486 sjacqu01
                if (args[sample] < this->bin_positions[1])
143 2486 sjacqu01
                {
144 2486 sjacqu01
                    ++(this->samples_in_bin[0]);
145 2486 sjacqu01
                }
146 2486 sjacqu01
                else if (args[sample] >= this->bin_positions[this->num_bins + 1])
147 2486 sjacqu01
                {
148 2486 sjacqu01
                    ++(this->samples_in_bin[this->num_bins + 1]);
149 2486 sjacqu01
                }
150 2486 sjacqu01
                else
151 2486 sjacqu01
                {
152 2486 sjacqu01
                    typename array_type::iterator it = std::upper_bound(
153 2486 sjacqu01
                        this->bin_positions.begin()
154 2486 sjacqu01
                      , this->bin_positions.end()
155 2486 sjacqu01
                      , args[sample]
156 2486 sjacqu01
                    );
157 2486 sjacqu01
158 2486 sjacqu01
                    std::size_t d = std::distance(this->bin_positions.begin(), it);
159 2486 sjacqu01
                    ++(this->samples_in_bin[d - 1]);
160 2486 sjacqu01
                }
161 2486 sjacqu01
            }
162 2486 sjacqu01
        }
163 2486 sjacqu01
164 2486 sjacqu01
        /**
165 2486 sjacqu01
            @pre The number of samples must meet or exceed the cache size
166 2486 sjacqu01
        */
167 2486 sjacqu01
        template<typename Args>
168 2486 sjacqu01
        result_type result(Args const &args) const
169 2486 sjacqu01
        {
170 2486 sjacqu01
            if (this->is_dirty)
171 2486 sjacqu01
            {
172 2486 sjacqu01
                this->is_dirty = false;
173 2486 sjacqu01
174 2486 sjacqu01
                // creates a vector of std::pair where each pair i holds
175 2486 sjacqu01
                // the values bin_positions[i] (x-axis of histogram) and
176 2486 sjacqu01
                // samples_in_bin[i] / cnt (y-axis of histogram).
177 2486 sjacqu01
178 2486 sjacqu01
                for (std::size_t i = 0; i < this->num_bins + 2; ++i)
179 2486 sjacqu01
                {
180 2486 sjacqu01
                    this->histogram[i] = std::make_pair(this->bin_positions[i], numeric::fdiv(this->samples_in_bin[i], count(args)));
181 2486 sjacqu01
                }
182 2486 sjacqu01
            }
183 2486 sjacqu01
            // returns a range of pairs
184 2486 sjacqu01
            return make_iterator_range(this->histogram);
185 2486 sjacqu01
        }
186 2486 sjacqu01
187 2486 sjacqu01
    private:
188 2486 sjacqu01
        std::size_t            cache_size;      // number of cached samples
189 2486 sjacqu01
        array_type             cache;           // cache to store the first cache_size samples
190 2486 sjacqu01
        std::size_t            num_bins;        // number of bins
191 2486 sjacqu01
        array_type             samples_in_bin;  // number of samples in each bin
192 2486 sjacqu01
        array_type             bin_positions;   // lower bounds of bins
193 2486 sjacqu01
        mutable histogram_type histogram;       // histogram
194 2486 sjacqu01
        mutable bool is_dirty;
195 2486 sjacqu01
    };
196 2486 sjacqu01
197 2486 sjacqu01
} // namespace impl
198 2486 sjacqu01
199 2486 sjacqu01
///////////////////////////////////////////////////////////////////////////////
200 2486 sjacqu01
// tag::density
201 2486 sjacqu01
//
202 2486 sjacqu01
namespace tag
203 2486 sjacqu01
{
204 2486 sjacqu01
    struct density
205 2486 sjacqu01
      : depends_on<count, min, max>
206 2486 sjacqu01
      , density_cache_size
207 2486 sjacqu01
      , density_num_bins
208 2486 sjacqu01
    {
209 2486 sjacqu01
        /// INTERNAL ONLY
210 2486 sjacqu01
        ///
211 2486 sjacqu01
        typedef accumulators::impl::density_impl<mpl::_1> impl;
212 2486 sjacqu01
213 2486 sjacqu01
        #ifdef BOOST_ACCUMULATORS_DOXYGEN_INVOKED
214 2486 sjacqu01
        /// tag::density::cache_size named parameter
215 2486 sjacqu01
        /// tag::density::num_bins named parameter
216 2486 sjacqu01
        static boost::parameter::keyword<density_cache_size> const cache_size;
217 2486 sjacqu01
        static boost::parameter::keyword<density_num_bins> const num_bins;
218 2486 sjacqu01
        #endif
219 2486 sjacqu01
    };
220 2486 sjacqu01
}
221 2486 sjacqu01
222 2486 sjacqu01
///////////////////////////////////////////////////////////////////////////////
223 2486 sjacqu01
// extract::density
224 2486 sjacqu01
//
225 2486 sjacqu01
namespace extract
226 2486 sjacqu01
{
227 2486 sjacqu01
    extractor<tag::density> const density = {};
228 2486 sjacqu01
229 2486 sjacqu01
    BOOST_ACCUMULATORS_IGNORE_GLOBAL(density)
230 2486 sjacqu01
}
231 2486 sjacqu01
232 2486 sjacqu01
using extract::density;
233 2486 sjacqu01
234 2486 sjacqu01
// So that density can be automatically substituted
235 2486 sjacqu01
// with weighted_density when the weight parameter is non-void.
236 2486 sjacqu01
template<>
237 2486 sjacqu01
struct as_weighted_feature<tag::density>
238 2486 sjacqu01
{
239 2486 sjacqu01
    typedef tag::weighted_density type;
240 2486 sjacqu01
};
241 2486 sjacqu01
242 2486 sjacqu01
template<>
243 2486 sjacqu01
struct feature_of<tag::weighted_density>
244 2486 sjacqu01
  : feature_of<tag::density>
245 2486 sjacqu01
{
246 2486 sjacqu01
};
247 2486 sjacqu01
248 2486 sjacqu01
}} // namespace boost::accumulators
249 2486 sjacqu01
250 2486 sjacqu01
#endif