Class AliasTable

Walker's Alias Method implementation for O(1) weighted random selection.

Inheritance
object
AliasTable
Inherited Members
Namespace: Scylla.Core.Util.Random
Assembly: ScyllaCore.dll
Syntax
public sealed class AliasTable
Remarks

The alias method preprocesses a set of normalized probabilities into two parallel arrays - a probability table and an alias table - so that each sample requires only a random column selection and a biased coin flip. Build cost is O(n); each subsequent sample is O(1) using exactly two uniform random numbers.

This class allocates arrays only when the entry count grows, reusing existing buffers on repeated builds of the same or smaller size. The temporary working arrays (_scaled, _small, _large) are instance-owned to avoid static state and thread-safety concerns.

This table is used internally by ProbabilityList<T> when its Strategy is set to AliasTable.

Properties

Count

The number of entries currently stored in this alias table. Returns zero until Build(float[], int) is called with a positive count.

Declaration
public int Count { get; }
Property Value
Type Description
int

Methods

Build(float[], int)

Builds the alias table from a set of normalized probabilities.

Declaration
public void Build(float[] probabilities, int count)
Parameters
Type Name Description
float[] probabilities

Array of per-entry probabilities. Only the first count elements are read. All values must be non-negative.
int count

The number of entries to read from probabilities. If zero or negative, the table is cleared and no work is done.
Remarks

Input probabilities must be non-negative and should sum to approximately 1.0. If probabilities do not sum to 1.0 due to floating-point imprecision, residual entries are clamped to probability 1 at the end of the build pass.

Internal arrays are only reallocated when count exceeds the current buffer capacity, allowing repeated calls to reuse existing memory.

Exceptions
Type Condition
ArgumentNullException

Thrown when probabilities is null.

Sample(IRandomSource)

Samples a single entry index from the alias table in O(1) time.

Declaration
public int Sample(IRandomSource rng)
Parameters
Type Name Description
IRandomSource rng

The random source used to generate the two uniform values. Must not be null.
Returns
Type Description
int

A zero-based entry index in the range [0, Count) selected according to the weighted distribution, or -1 if the table is empty (i.e., Count is zero).
Remarks

Two uniform random values are consumed per call: one to select a column uniformly at random, and one for a biased coin flip that determines whether to return the column's primary entry or its alias. This gives each entry a selection probability proportional to the weights provided when Build(float[], int) was called.

Extension Methods