RandomLib::RandomSelect Class Reference

Random selection from a discrete set. More...

#include <RandomLib-2010-01/RandomSelect.hpp>

List of all members.

Public Member Functions
	RandomSelect () throw (std::bad_alloc)
template<typename WeightType >
	RandomSelect (const std::vector< WeightType > &w) throw (std::out_of_range, std::bad_alloc)
template<typename InputIterator >
	RandomSelect (InputIterator a, InputIterator b) throw (std::out_of_range, std::bad_alloc)
void	Init () throw ()
template<typename WeightType >
void	Init (const std::vector< WeightType > &w) throw (std::out_of_range, std::bad_alloc)
template<typename InputIterator >
void	Init (InputIterator a, InputIterator b) throw (std::out_of_range, std::bad_alloc)
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 ()
Private Attributes
unsigned	_k
std::vector< NumericType >	_Q
std::vector< unsigned >	_Y
NumericType	_wsum
NumericType	_wmax

---

Detailed Description

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(k²) 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:

   #include "RandomLib/RandomSelect.hpp"

   // Weights for throwing a pair of dice
   unsigned w[] = { 0, 0, 1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1 };

   // Initialize selection
   RandomLib::RandomSelect<unsigned> sel(w, w + 13);

   RandomLib::Random r;   // Initialize random numbers
   std::cout << "Seed set to " << r.SeedString() << std::endl;

   std::cout << "Throw a pair of dice 100 times:";
   for (unsigned i = 0; i < 100; ++i)
       std::cout << " " << sel(r);
   std::cout << std::endl;

---

Constructor & Destructor Documentation

RandomLib::RandomSelect::RandomSelect

(

)

throw (std::bad_alloc) [inline]

Initialize in a cleared state (equivalent to having a single choice).

Definition at line 73 of file RandomSelect.hpp.

template<typename WeightType >

RandomLib::RandomSelect::RandomSelect

(

const std::vector< WeightType > &

w

)

throw (std::out_of_range, std::bad_alloc) [inline]

Initialize with a weight vector w of elements of type WeightType. Internal calculations are carried out with type NumericType. NumericType needs to allow Choices() * MaxWeight() to be represented. Sensible combinations are:

• WeightType integer, NumericType integer with digits(NumericType) >= digits(WeightType)
• WeightType integer, NumericType real
• WeightType real, NumericType real with digits(NumericType) >= digits(WeightType)

Definition at line 87 of file RandomSelect.hpp.

References Init().

template<typename InputIterator >

RandomLib::RandomSelect::RandomSelect	(	InputIterator	a,
		InputIterator	b
	)		throw (std::out_of_range, std::bad_alloc)

Initialize with a weight given by a pair of iterators [a, b).

Definition at line 204 of file RandomSelect.hpp.

References STATIC_ASSERT.

---

Member Function Documentation

void RandomLib::RandomSelect::Init

(

)

throw () [inline]

Clear the state (equivalent to having a single choice).

Definition at line 101 of file RandomSelect.hpp.

References _k, _wsum, _wmax, _Q, and _Y.

Referenced by RandomSelect().

template<typename WeightType >

void RandomLib::RandomSelect::Init

(

const std::vector< WeightType > &

w

)

throw (std::out_of_range, std::bad_alloc) [inline]

Re-initialize with a weight vector w. Leave state unaltered in the case of an error.

Definition at line 109 of file RandomSelect.hpp.

References Init().

Referenced by Init().

template<typename InputIterator >

void RandomLib::RandomSelect::Init	(	InputIterator	a,
		InputIterator	b
	)		throw (std::out_of_range, std::bad_alloc) [inline]

Re-initialize with a weight given as a pair of iterators [a, b). Leave state unaltered in the case of an error.

Definition at line 117 of file RandomSelect.hpp.

References _Q, and _Y.

template<class Random >

unsigned RandomLib::RandomSelect::operator()

(

Random &

r

)

const throw () [inline]

Return an index into the weight vector with probability proportional to the weight.

Definition at line 130 of file RandomSelect.hpp.

References _k, _Q, _wsum, and _Y.

NumericType RandomLib::RandomSelect::TotalWeight

(

)

const throw () [inline]

Return the sum of the weights.

Definition at line 146 of file RandomSelect.hpp.

References _wsum.

NumericType RandomLib::RandomSelect::MaxWeight

(

)

const throw () [inline]

Return the maximum weight.

Definition at line 151 of file RandomSelect.hpp.

References _wmax.

NumericType RandomLib::RandomSelect::Weight

(

unsigned

i

)

const throw () [inline]

Return the weight for sample i. Weight(i) / TotalWeight() gives the probability of sample i.

Definition at line 157 of file RandomSelect.hpp.

References _k, _wsum, _Q, and _Y.

unsigned RandomLib::RandomSelect::Choices

(

)

const throw () [inline]

Return the number of choices, i.e., the length of the weight vector.

Definition at line 176 of file RandomSelect.hpp.

References _k.

---

Member Data Documentation

unsigned RandomLib::RandomSelect::_k [private]

Size of weight vector

Definition at line 183 of file RandomSelect.hpp.

Referenced by Init(), operator()(), Weight(), and Choices().

std::vector<NumericType> RandomLib::RandomSelect::_Q [private]

Vector of cutoffs

Definition at line 187 of file RandomSelect.hpp.

Referenced by Init(), operator()(), and Weight().

std::vector<unsigned> RandomLib::RandomSelect::_Y [private]

Vector of aliases

Definition at line 191 of file RandomSelect.hpp.

Referenced by Init(), operator()(), and Weight().

NumericType RandomLib::RandomSelect::_wsum [private]

The sum of the weights

Definition at line 195 of file RandomSelect.hpp.

Referenced by Init(), operator()(), TotalWeight(), and Weight().

NumericType RandomLib::RandomSelect::_wmax [private]

The maximum weight

Definition at line 199 of file RandomSelect.hpp.

Referenced by Init(), and MaxWeight().

---

The documentation for this class was generated from the following file:

• RandomSelect.hpp