|
| | RandomSelect () |
| |
| template<typename WeightType > |
| | RandomSelect (const std::vector< WeightType > &w) |
| |
| template<typename InputIterator > |
| | RandomSelect (InputIterator a, InputIterator b) |
| |
| void | Init () throw () |
| |
| template<typename WeightType > |
| void | Init (const std::vector< WeightType > &w) |
| |
| template<typename InputIterator > |
| void | Init (InputIterator a, InputIterator b) |
| |
| template<class Random > |
| unsigned | operator() (Random &r) const throw () |
| |
| NumericType | TotalWeight () const throw () |
| |
| NumericType | MaxWeight () const throw () |
| |
| NumericType | Weight (unsigned i) const throw () |
| |
| unsigned | Choices () const throw () |
| |
template<typename NumericType = double>
class RandomLib::RandomSelect< NumericType >
Random selection from a discrete set.
An implementation of Walker algorithm for selecting from a finite set (following Knuth, TAOCP, Vol 2, Sec 3.4.1.A). This provides a rapid way of selecting one of several choices depending on a discrete set weights. Original citation is
A. J. Walker,
An Efficient Method for Generating Discrete Random Variables and General Distributions,
ACM TOMS 3, 253–256 (1977).
There are two changes here in the setup algorithm as given by Knuth:
- The probabilities aren't sorted at the beginning of the setup; nor are they maintained in a sorted order. Instead they are just partitioned on the mean. This improves the setup time from O(k2) to O(k).
- The internal calculations are carried out with type NumericType. If the input weights are of integer type, then choosing an integer type for NumericType yields an exact solution for the returned distribution (assuming that the underlying random generator is exact.)
Example:
unsigned w[] = { 0, 0, 1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1 };
std::cout << "Seed set to " << r.SeedString() << "\n";
std::cout << "Throw a pair of dice 100 times:";
for (unsigned i = 0; i < 100; ++i)
std::cout << " " << sel(r);
std::cout << "\n";
- Template Parameters
-
| NumericType | the numeric type to use (default double). |
Definition at line 69 of file RandomSelect.hpp.
1.8.6
