Function cmb_random_alias_sample

• Defined in File cmb_random.h

Function Documentation

static inline unsigned cmb_random_alias_sample(const struct cmb_random_alias *ap)

Perform alias sampling, a more efficient way of sampling a non-uniform discrete distribution of n alternatives. Returns values on [0, (pa->n) - 1], typically used for array indices and the like.

Does the same as cmb_random_loaded_dice(), but at O(1) in each draw, at the cost of an initial O(n) initialization by cmb_random_alias_create().

See also https://en.wikipedia.org/wiki/Alias_method https://pbr-book.org/4ed/Sampling_Algorithms/The_Alias_Method or (especially) https://www.keithschwarz.com/darts-dice-coins/

Call cmb_random_alias_create() first to allocate and return a look-up table of (prob, alias) pairs, cmb_random_alias_destroy() to free the memory when finished.

Parameters:

• ap – Pointer to an allocated and initialized cmb_random_alias look-up table.

Returns:

A randomly chosen index into the table, selected with a probability pa[i]