# AliasTables.jl

**URL:** <https://discourse.julialang.org/t/aliastables-jl/112884>\
**Category:** Package Announcements\
**Created:** [April 12, 2024, 3:58pm UTC](https://discourse.julialang.org/t/aliastables-jl/112884 "2024-04-12T15:58:13Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [April 12, 2024, 3:58pm UTC](https://discourse.julialang.org/t/aliastables-jl/112884/1 "2024-04-12T15:58:13Z")

</div>

Heyo!

I’m announcing a state of the art high performance implementation of the alias method for categorical non-uniform random sampling over `1:n` with O(1) sampling time and O(n) setup time.

Docs: [https://aliastables.lilithhafner.com](https://aliastables.lilithhafner.com)  
Source: [GitHub - LilithHafner/AliasTables.jl: An efficient sampler for discrete random variables](https://github.com/LilithHafner/AliasTables.jl)

Enjoy 🙂

Happy to hear feedback and pointers to other implementations of this algorithm

Here’s a performance teaser

```julia
julia> using AliasTables, Chairmarks

julia> at = AliasTable(rand(17));

julia> @b rand($at)
2.878 ns

julia> @b rand(UInt64)
2.723 ns

julia> @b rand(1:17)
3.414 ns

```

---

<div class="post-metadata">

**Author:** ![TheCedarPrince](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/thecedarprince/32/17323_2.png) [@TheCedarPrince](https://discourse.julialang.org/u/TheCedarPrince)\
**Post date:** [April 12, 2024, 4:32pm UTC](https://discourse.julialang.org/t/aliastables-jl/112884/2 "2024-04-12T16:32:56Z")

</div>

Oh my gosh, new @Lilith package just dropped! 😱

Out of curiosity, how does this compare to the sampling methods over in Statistics or StatsBase? I have no idea how they compare or how I would make a comparison so apologies for the vague question. I tend to just use the `sample` method from `StatsBase` so was curious.

Always excited to see whenever you have a new experimental package up!

Cheers,

~ tcp 🌳

---

<div class="post-metadata">

**Author:** ![vancleve](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/vancleve/32/4183_2.png) [@vancleve](https://discourse.julialang.org/u/vancleve)\
**Post date:** [April 12, 2024, 8:14pm UTC](https://discourse.julialang.org/t/aliastables-jl/112884/3 "2024-04-12T20:14:08Z")

</div>

Its a very nice improvement!

> <https://github.com/JuliaStats/StatsBase.jl/pull/927#issue-2231349735>
>
> Safer:
> 
> Before
> 
> \`\`\`julia
> julia\> StatsBase.alias\_sample!(rand(10), weights(r…andn(10)), rand(10))
> 10-element Vector{Float64}:
> 0.5676653052762575
> 0.5676653052762575
> 0.5676653052762575
> 0.5676653052762575
> 0.5676653052762575
> 0.5676653052762575
> 0.1984287484280587
> 0.5676653052762575
> 0.1984287484280587
> 0.8567391687334422
> 
> julia\> StatsBase.alias\_sample!(rand(10), weights(fill(0, 10)), rand(10))
> ERROR: BoundsError: attempt to access 10-element Vector{Float64} at index \[281471800382896\] # This came from reading undef memory
> Stacktrace:
> \[1\] throw\_boundserror(A::Vector{Float64}, I::Tuple{Int64})
> @ Base ./essentials.jl:14
> \[2\] getindex
> @ ./essentials.jl:891 \[inlined\]
> \[3\] alias\_sample!(rng::TaskLocalRNG, a::Vector{Float64}, wv::Weights{Int64, Int64, Vector{Int64}}, x::Vector{Float64})
> @ StatsBase ~/.julia/packages/StatsBase/ebrT3/src/sampling.jl:729
> \[4\] top-level scope
> @ REPL\[10\]:1
> 
> julia\> StatsBase.alias\_sample!(rand(10), weights(fill(0, 10)), rand(10)) # Got "lucky" this time
> 10-element Vector{Float64}:
> 0.07577419536126007
> 0.9233876530591941
> 0.1530016664475169
> 0.07577419536126007
> 0.07577419536126007
> 0.3159766423652197
> 0.1530016664475169
> 0.6780730450968911
> 0.01012788415877619
> 0.6780730450968911
> \`\`\`
> 
> After
> 
> \`\`\`julia
> julia\> StatsBase.alias\_sample!(rand(10), weights(randn(10)), rand(10))
> ERROR: ArgumentError: found negative weight -0.1164833812103052
> Stacktrace:
> \[1\] checked\_sum
> @ ~/.julia/packages/AliasTables/yt2Qj/src/AliasTables.jl:437 \[inlined\]
> \[2\] AliasTables.AliasTable{UInt64, Int64}(weights::Weights{Float64, Float64, Vector{Float64}}; \_normalize::Bool)
> @ AliasTables ~/.julia/packages/AliasTables/yt2Qj/src/AliasTables.jl:81
> \[3\] AliasTable
> @ ~/.julia/packages/AliasTables/yt2Qj/src/AliasTables.jl:78 \[inlined\]
> \[4\] AliasTable
> @ ~/.julia/packages/AliasTables/yt2Qj/src/AliasTables.jl:76 \[inlined\]
> \[5\] alias\_sample!(rng::TaskLocalRNG, a::Vector{Float64}, wv::Weights{Float64, Float64, Vector{Float64}}, x::Vector{Float64})
> @ StatsBase ~/.julia/dev/StatsBase/src/sampling.jl:719
> \[6\] top-level scope
> @ REPL\[33\]:1
> 
> julia\> StatsBase.alias\_sample!(rand(10), weights(fill(0, 10)), rand(10))
> ERROR: ArgumentError: all weights are zero
> Stacktrace:
> \[1\] checked\_sum
> @ ~/.julia/packages/AliasTables/yt2Qj/src/AliasTables.jl:418 \[inlined\]
> \[2\] AliasTables.AliasTable{UInt64, Int64}(weights::Weights{Int64, Int64, Vector{Int64}}; \_normalize::Bool)
> @ AliasTables ~/.julia/packages/AliasTables/yt2Qj/src/AliasTables.jl:81
> \[3\] AliasTable
> @ ~/.julia/packages/AliasTables/yt2Qj/src/AliasTables.jl:78 \[inlined\]
> \[4\] AliasTable
> @ ~/.julia/packages/AliasTables/yt2Qj/src/AliasTables.jl:76 \[inlined\]
> \[5\] alias\_sample!(rng::TaskLocalRNG, a::Vector{Float64}, wv::Weights{Int64, Int64, Vector{Int64}}, x::Vector{Float64})
> @ StatsBase ~/.julia/dev/StatsBase/src/sampling.jl:719
> \[6\] top-level scope
> @ REPL\[38\]:1
> \`\`\`
> 
> Faster (benchmarks from https://github.com/JuliaStats/StatsBase.jl/issues/695#issuecomment-853816909)
> 
> Before
> \`\`\`julia
> julia\> using Chairmarks
> 
> julia\> @b sample(1:5030, StatsBase.Weights(rand(Float32,5030)), 141230, replace=true)
> 1.558 ms (19 allocs: 1.251 MiB)
> 
> julia\> @b sample(1:5030, StatsBase.Weights(rand(Float64,5030)), 141230, replace=true)
> 1.575 ms (19 allocs: 1.270 MiB)
> \`\`\`
> 
> After
> \`\`\`julia
> julia\> @b sample(1:5030, StatsBase.Weights(rand(Float32,5030)), 141230, replace=true)
> 294.460 μs (12 allocs: 1.260 MiB)
> 
> julia\> @b sample(1:5030, StatsBase.Weights(rand(Float64,5030)), 141230, replace=true)
> 296.418 μs (12 allocs: 1.280 MiB)
> \`\`\`
> 
> Closes #630 (AliasTables.jl \[uses \`@inbounds\` in sampling\](https://github.com/LilithHafner/AliasTables.jl/blob/cb7b2d64bae60b92931cd1ddadfcfd20a8d0ba91/src/AliasTables.jl#L255) and contains a \[correctness proof\](https://github.com/LilithHafner/AliasTables.jl/blob/cb7b2d64bae60b92931cd1ddadfcfd20a8d0ba91/src/AliasTables.jl#L260-L300) that relies only on local information and basic properties of unsigned integers)
> 
> Closes #916 by making \`alias\_sample!\` much faster than even using \`ifelse\` would. See https://aliastables.lilithhafner.com/dev/#Implementation-details for how.
> 
> See also: https://github.com/JuliaStats/Distributions.jl/pull/1848
> 
> cc @devmotion

Thanks @Lilith for the hard work!

---

<div class="post-metadata">

**Author:** ![Lilith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lilith/32/27492_2.png) [@Lilith](https://discourse.julialang.org/u/Lilith)\
**Post date:** [April 12, 2024, 9:59pm UTC](https://discourse.julialang.org/t/aliastables-jl/112884/4 "2024-04-12T21:59:25Z")

</div>

The PR @vancleve linked to has more details, but TL;DR is it’s almost always faster and so now StatsBase.jl does use it, and Distributions.jl will likely soon ([Use a faster implementation of AliasTables by LilithHafner · Pull Request #1848 · JuliaStats/Distributions.jl · GitHub](https://github.com/JuliaStats/Distributions.jl/pull/1848))

Some reasons one might use AliasTables.jl directly are load time/dependency reduction, or to implement very high performance samplers for downstream types that take advantage of implementation details of the underlying rng (e.g. xoshiro’s bulk generation)