| Directory: | ./ |
|---|---|
| File: | include/hpp/statistics/distribution.hh |
| Date: | 2025-03-06 12:03:19 |
| Exec | Total | Coverage | |
|---|---|---|---|
| Lines: | 36 | 55 | 65.5% |
| Branches: | 18 | 38 | 47.4% |
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | // Copyright (c) 2014, LAAS-CNRS | ||
| 2 | // Authors: Joseph Mirabel (joseph.mirabel@laas.fr) | ||
| 3 | // | ||
| 4 | // This file is part of hpp-statistics. | ||
| 5 | // hpp-statistics is free software: you can redistribute it | ||
| 6 | // and/or modify it under the terms of the GNU Lesser General Public | ||
| 7 | // License as published by the Free Software Foundation, either version | ||
| 8 | // 3 of the License, or (at your option) any later version. | ||
| 9 | // | ||
| 10 | // hpp-statistics is distributed in the hope that it will be | ||
| 11 | // useful, but WITHOUT ANY WARRANTY; without even the implied warranty | ||
| 12 | // of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | ||
| 13 | // General Lesser Public License for more details. You should have | ||
| 14 | // received a copy of the GNU Lesser General Public License along with | ||
| 15 | // hpp-statistics. If not, see <http://www.gnu.org/licenses/>. | ||
| 16 | |||
| 17 | #ifndef HPP_STATISTICS_DISTRIBUTION_HH | ||
| 18 | #define HPP_STATISTICS_DISTRIBUTION_HH | ||
| 19 | |||
| 20 | #include <assert.h> | ||
| 21 | #include <stdlib.h> | ||
| 22 | |||
| 23 | #include <climits> | ||
| 24 | #include <vector> | ||
| 25 | |||
| 26 | #include "hpp/statistics/fwd.hh" | ||
| 27 | |||
| 28 | namespace hpp { | ||
| 29 | namespace statistics { | ||
| 30 | template <typename Value_t> | ||
| 31 | class DiscreteDistribution { | ||
| 32 | public: | ||
| 33 | typedef std::size_t Weight_t; | ||
| 34 | typedef typename std::pair<Weight_t, Value_t> ProbaTPair; | ||
| 35 | typedef typename std::vector<ProbaTPair>::iterator iterator; | ||
| 36 | typedef typename std::vector<ProbaTPair>::const_iterator const_iterator; | ||
| 37 | |||
| 38 | 1 | DiscreteDistribution() = default; | |
| 39 | |||
| 40 | Value_t operator()() const { | ||
| 41 | assert(values_.size() > 0); | ||
| 42 | Weight_t r = rand() % cumulative_weights_.back(); | ||
| 43 | return operator()(r); | ||
| 44 | } | ||
| 45 | Value_t operator()(const Proba_t& p) const { | ||
| 46 | return operator()((Weight_t)(p * cumulative_weights_.back())); | ||
| 47 | } | ||
| 48 | 2 | Value_t operator()(const Weight_t& w) const { | |
| 49 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
|
2 | assert(values_.size() > 0); |
| 50 | 2 | return values_[dichotomy(w % cumulative_weights_.back())].second; | |
| 51 | } | ||
| 52 | |||
| 53 | /// Update the distribution. | ||
| 54 | /// If v is already in the set, then update its weight. | ||
| 55 | /// Otherwise, insert it. | ||
| 56 | 3 | void insert(Value_t v, Weight_t w = 1) { | |
| 57 | 3 | iterator itv = values_.begin(); | |
| 58 | 3 | WeightsIterator itcumul = cumulative_weights_.begin(); | |
| 59 | 3 | Weight_t c = 0; | |
| 60 |
2/2✓ Branch 2 taken 3 times.
✓ Branch 3 taken 3 times.
|
6 | while (itv != values_.end()) { |
| 61 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 3 times.
|
3 | if (itv->second == v) break; |
| 62 | 3 | c = *itcumul; | |
| 63 | 3 | itv++; | |
| 64 | 3 | itcumul++; | |
| 65 | } | ||
| 66 |
1/2✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
|
3 | if (itv == values_.end()) { |
| 67 |
1/2✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
|
3 | values_.push_back(ProbaTPair(w, v)); |
| 68 |
1/2✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
|
3 | cumulative_weights_.push_back(c + w); |
| 69 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 3 times.
|
3 | if (cumulative_weights_.back() >= INT_MAX / 2) shrink(); |
| 70 | 3 | return; | |
| 71 | } | ||
| 72 | ✗ | itv->first = w; | |
| 73 | ✗ | while (itv != values_.end()) { | |
| 74 | ✗ | c = c + itv->first; | |
| 75 | ✗ | *itcumul = c; | |
| 76 | ✗ | itv++; | |
| 77 | ✗ | itcumul++; | |
| 78 | } | ||
| 79 | ✗ | if (cumulative_weights_.back() >= INT_MAX / 2) shrink(); | |
| 80 | } | ||
| 81 | |||
| 82 | /// Get the weight of a value | ||
| 83 | /// Return 0 if value was not found. | ||
| 84 | Weight_t get(const Value_t& v) const { | ||
| 85 | const_iterator itv = values_.begin(); | ||
| 86 | while (itv != values_.end()) { | ||
| 87 | if (itv->second == v) return itv->first; | ||
| 88 | itv++; | ||
| 89 | } | ||
| 90 | return 0; | ||
| 91 | } | ||
| 92 | |||
| 93 | /// Return the number of value. | ||
| 94 | size_t size() const { return values_.size(); } | ||
| 95 | |||
| 96 | /// Return the probabilities. | ||
| 97 | 1 | std::vector<Proba_t> probabilities() const { | |
| 98 |
1/4✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
|
1 | if (values_.empty()) return std::vector<Proba_t>(0); |
| 99 |
1/2✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
|
1 | std::vector<Proba_t> proba(values_.size()); |
| 100 | 1 | Proba_t total = (double)cumulative_weights_.back(); | |
| 101 |
2/2✓ Branch 1 taken 3 times.
✓ Branch 2 taken 1 times.
|
4 | for (size_t i = 0; i < values_.size(); i++) |
| 102 | 3 | proba[i] = (Proba_t)values_[i].first / total; | |
| 103 | 1 | return proba; | |
| 104 | 1 | } | |
| 105 | |||
| 106 | /// Return the values. | ||
| 107 | std::vector<Value_t> values() const { | ||
| 108 | if (values_.empty()) return std::vector<Value_t>(0); | ||
| 109 | std::vector<Value_t> v(values_.size()); | ||
| 110 | for (size_t i = 0; i < values_.size(); i++) v[i] = values_[i].second; | ||
| 111 | return v; | ||
| 112 | } | ||
| 113 | |||
| 114 | /// Return the total weight. | ||
| 115 | Weight_t totalWeight() const { | ||
| 116 | if (cumulative_weights_.empty()) return 0; | ||
| 117 | return cumulative_weights_.back(); | ||
| 118 | } | ||
| 119 | |||
| 120 | /// \name Iterators | ||
| 121 | /// Iterate on the values. | ||
| 122 | /// \{ | ||
| 123 | iterator begin() { return values_.begin(); } | ||
| 124 | const_iterator begin() const { return values_.begin(); } | ||
| 125 | iterator end() { return values_.end(); } | ||
| 126 | const_iterator end() const { return values_.end(); } | ||
| 127 | /// \} | ||
| 128 | private: | ||
| 129 | 2 | size_t dichotomy(const Weight_t& r) const { | |
| 130 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 2 times.
|
2 | if (r < cumulative_weights_[0]) return 0; |
| 131 | 2 | size_t l = 0, h = values_.size() - 1, m; | |
| 132 |
2/2✓ Branch 0 taken 2 times.
✓ Branch 1 taken 2 times.
|
4 | while (l < h - 1) { |
| 133 | 2 | m = (l + h) / 2; | |
| 134 |
2/2✓ Branch 1 taken 1 times.
✓ Branch 2 taken 1 times.
|
2 | if (cumulative_weights_[m] <= r) |
| 135 | 1 | l = m; | |
| 136 |
1/2✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
|
1 | else if (cumulative_weights_[m] > r) |
| 137 | 1 | h = m; | |
| 138 | else | ||
| 139 | ✗ | return m; | |
| 140 | } | ||
| 141 | 2 | return h; | |
| 142 | } | ||
| 143 | |||
| 144 | /// Diminish the weights while keeping their ratio. | ||
| 145 | ✗ | void shrink() { | |
| 146 | ✗ | iterator itv = values_.begin(); | |
| 147 | ✗ | WeightsIterator itcumul = cumulative_weights_.begin(); | |
| 148 | ✗ | Weight_t total = 0; | |
| 149 | ✗ | while (itv != values_.end()) { | |
| 150 | ✗ | if (itv->first > 1) { | |
| 151 | ✗ | itv->first = itv->first >> 1; | |
| 152 | } | ||
| 153 | ✗ | total += itv->first; | |
| 154 | ✗ | *itcumul = total; | |
| 155 | ✗ | itv++; | |
| 156 | ✗ | itcumul++; | |
| 157 | } | ||
| 158 | } | ||
| 159 | |||
| 160 | std::vector<ProbaTPair> values_; | ||
| 161 | std::vector<Weight_t> cumulative_weights_; | ||
| 162 | |||
| 163 | typedef std::vector<Weight_t>::iterator WeightsIterator; | ||
| 164 | }; | ||
| 165 | } // namespace statistics | ||
| 166 | } // namespace hpp | ||
| 167 | |||
| 168 | #endif // HPP_STATISTICS_DISTRIBUTION_HH | ||
| 169 |