Stride Reference Manual  1.0
AliasDistribution.cpp
Go to the documentation of this file.
1 #include "AliasDistribution.h"
2 #include <cassert>
3 #include <numeric>
4 
5 using namespace stride;
6 using namespace util;
7 
8 AliasDistribution::AliasDistribution(const vector<double>& _probs)
9  : m_blocks(_probs.size()), m_diceroll(0, _probs.size() - 1) {
10  double factor = 1.0 / std::accumulate(_probs.begin(), _probs.end(), 0.0);
11 
12  unsigned int n = _probs.size();
13  assert(n > 0);
14  vector<double> probs(n);
15  for (unsigned int i = 0; i < n; i++) probs[i] = _probs[i] * factor * n;
16 
17  deque<unsigned int> small, large;
18  for (unsigned int i = 0; i < n; i++) {
19  (probs[i] < 1.0 ? small : large).push_back(i);
20  }
21 
22  while ((not small.empty()) and (not large.empty())) {
23  unsigned int l = *small.begin();
24  small.pop_front();
25  unsigned int g = *large.begin();
26  large.pop_front();
27 
28  m_blocks[l].prob = probs[l];
29  m_blocks[l].alias = g;
30  probs[g] = (probs[g] + probs[l]) - 1;
31  (probs[g] < 1.0 ? small : large).push_back(g);
32  }
33 
34  for (unsigned int i: large) m_blocks[i].prob = 1.0;
35  // If small is not empty, this may be sign of numerical instability
36  for (unsigned int i: small) m_blocks[i].prob = 1.0;
37 }
38 
39 uniform_real_distribution<double> AliasDistribution::g_coinflip = uniform_real_distribution<double>(0, 1);
40 
41 template<typename K, typename V>
42 vector<V> map_values(const map<K, V>& m) {
43  vector<V> v;
44  v.reserve(m.size());
45  for (const auto& it: m) {
46  v.push_back(it.second);
47  }
48  return v;
49 };
50 
51 MappedAliasDistribution::MappedAliasDistribution(const map<unsigned int, double>& m)
53  unsigned int k = 0;
54  for (const auto& it: m) {
55  m_translation[k] = it.first;
56  k++;
57  }
58 }
Usage is very simple, construct with a vector of probabilities, then use as a distribution from the s...
static uniform_real_distribution< double > g_coinflip
Time Dependent Person DataType.
Definition: NoBehaviour.h:17
map< unsigned int, unsigned int > m_translation
vector< V > map_values(const map< K, V > &m)