AliasTables provides the AliasTable type, which is an object that defines a probability
distribution over 1:n for some n. They are efficient to construct and very efficient to
sample from.
An alias table can be combined with a dense vector of values to create a discrete distribution over anything.
Internally, AliasTables define a mapping from an unsigned integer type to the sampling
domain. To get a random sample according to the AliasTable's distribution, one must provide
a random unsigned integer uniformly at random. One can also provide a Random.AbstractRNG
object instead and a random unsigned integer will be generated using that rng. When using
the random API, this latter approach is taken.
julia> using AliasTables
julia> at = AliasTable([5,10,1])
AliasTable([0x5000000000000000, 0xa000000000000000, 0x1000000000000000])
julia> rand(at, 10)
10-element Vector{Int64}:
2
1
2
2
2
2
1
1
3
2
julia> using Chairmarks
julia> @b at rand
2.898 ns
julia> @b rand(UInt)
2.738 ns
julia> @b rand(1000) AliasTable
9.167 μs (2 allocs: 16.031 KiB)
julia> @b AliasTable(rand(1000)) rand(_, 1000)
1.506 μs (3 allocs: 7.875 KiB)
julia> @b AliasTable(rand(1000)), rand(1000) AliasTables.set_weights!(_...)
8.427 μs
julia> using StatsBase
julia> at = AliasTable{UInt16}([5,10,1])
AliasTable{UInt16}([0x5000, 0xa000, 0x1000])
julia> countmap(AliasTables.sample(x, at) for x in typemin(UInt16):typemax(UInt16))
Dict{Any, Int64} with 3 entries:
2 => 40960
3 => 4096
1 => 20480