tgen::weighted_sampler< T >

Sampler for repeated draws from a fixed weighted distribution. More...

Public Member Functions
	weighted_sampler (const std::vector< T > &distribution)
	Creates a weighted sampler from a probability distribution.
size_t	next () const
	Generates a random index with probability proportional to the distribution.

Detailed Description

template<typename T>
struct tgen::weighted_sampler< T >

Sampler for repeated draws from a fixed weighted distribution.

Builds, in O(n) time, a structure that produces independent indices i in [0, n - 1] with probability proportional to distribution[i], in O(1) per draw.

Internally uses the alias method. The internal weight type is selected from the input type T:

• if T is integral (int, long long, ...), all arithmetic is performed exactly in unsigned __int128, so distributions summing to nearly 2^128 are handled with no loss;
• if T is floating-point (float, double, ...), arithmetic is performed in double, with the small relative rounding error inherent to floating-point sums.

If only a single index is needed, prefer tgen::next_by_distribution. To draw k indices in one call, prefer tgen::many_by_distribution. Use tgen::weighted_sampler directly when many independent draws from the same distribution are needed but they cannot all be generated at once (for example, when the next draw depends on previous draws).

Examples

// Build the sampler once, draw many times. Integer weights.
tgen::weighted_sampler sampler(std::vector<int>{1, 3, 6});
for (int i = 0; i < 100; ++i)
    std::cout << sampler.next() << " ";
// Prints e.g. "2 1 2 0 2 1 1 2 2 1 2 2 1 2 2 ...".
 
// Fractional probabilities also work.
tgen::weighted_sampler probs(std::vector<double>{0.1, 0.3, 0.6});
size_t idx = probs.next();

Definition at line 822 of file tgen.h.

Constructor & Destructor Documentation

weighted_sampler()

template<typename T>

tgen::weighted_sampler< T >::weighted_sampler ( const std::vector< T > & distribution )

inline

Creates a weighted sampler from a probability distribution.

Template Parameters

T	Arithmetic type of the weights.

Parameters

distribution

Non-negative weights.

The probability of drawing index i is distribution[i] / sum(distribution).

Exceptions

std::runtime_error

if distribution is invalid.

Warning

For integral T, assumes that the sum of distribution fits in type unsigned __int128.

Complexity

O(|distribution|).

Examples

// Twice as likely to draw index 1 as index 0.
tgen::weighted_sampler sampler({1, 2});
 
// Same idea, expressed as fractional probabilities.
tgen::weighted_sampler probs({1.0 / 3, 2.0 / 3});

Definition at line 839 of file tgen.h.

Member Function Documentation

next()

template<typename T>

size_t tgen::weighted_sampler< T >::next ( ) const

inline

Generates a random index with probability proportional to the distribution.

Returns

An index i in [0, |distribution| - 1] with probability distribution[i] / sum(distribution).

Indices with weight 0 are never returned.

Complexity

O(1).

Examples

tgen::weighted_sampler sampler({1, 1000});
// Probability of returning "1" is 1000 times that of "0".
int idx = sampler.next();

Definition at line 905 of file tgen.h.

---

The documentation for this struct was generated from the following files:

• /home/runner/work/tgen/tgen/single_include/tgen.h
• base.dox