WAM

Pure Elixir implementation of Walker's Alias Method (WAM). It's method for performing weighted random sampling.

Installation

If available in Hex, the package can be installed by adding wam to your list of dependencies in mix.exs:

def deps do
  [
    {:wam, "~> 0.2.0"}
  ]
end

Upgrading from 0.1.x

The meaning of the public probs field has flipped. It used to hold the probability of taking the alias; it now holds the probability of keeping the bucket, so a draw reads if rng < probs[i], do: i, else: aliases[i]. Sampling through fetch/3, get/4 and index/3 behaves exactly as before — only code that reads wam.probs directly, or that passes a hand-picked rng to steer the comparison, is affected.

The reason for the change is a guarantee: a zero-weight atom is always paired away, so its probs entry is exactly 0.0, and rng < 0.0 is false for anyrng >= 0. A weight of 0 is therefore unreachable by construction, no longer depending on the generator staying strictly below 1.0. Code that mutes content by weighting it 0 can rely on that.

If you were calling get(wam, index, sentinel_rng) to read a slot without drawing, use at/3 instead — see below.

Usage

It supports both weights and probabilities.

wam = WAM.new(%{a: 10, b: 4, c: 5})
wam = WAM.new(%{a: 10 / 19, b: 4 / 19, c: 5 / 19})

Also it supports list of tuples and two lists:

wam = WAM.new([{:a, 10}, {:b, 4}, {:c, 5}])
wam = WAM.new([:a, :b, :c], [10, 4, 5])

And provides three functions to work with random sampling:

• fetch(wam, index, random) - to get weighted value in form of {:ok, value} or return {:error, reason} tuple in case of error.

  {:ok, value} = WAM.fetch(wam, :rand.uniform(wam.size) - 1, :rand.uniform())
  {:error, reason} = WAM.fetch(wam, :rand.uniform(wam.size) + 1, :rand.uniform())
  

• fetch(wam, index, random, default \\ nil) - to get weighted value or default value in case of error. The default value is nil unless otherwise specified.

  value = WAM.get(wam, :rand.uniform(wam.size) - 1, :rand.uniform())
  nil = WAM.get(wam, :rand.uniform(wam.size) + 1, :rand.uniform())
  value = WAM.get(wam, :rand.uniform(wam.size) - 1, :rand.uniform(), :default)
  :default = WAM.get(wam, :rand.uniform(wam.size) + 1, :rand.uniform(), :default)
  

• index(wam, index, random) - to get weighted index in form of {:ok, value} or return {:error, reason} tuple in case of error

  {:ok, index} = WAM.fetch(wam, :rand.uniform(wam.size) - 1, :rand.uniform())
  {:error, reason} = WAM.fetch(wam, :rand.uniform(wam.size) + 1, :rand.uniform())
  

And two functions to read a slot without drawing at all:

• at(wam, index, default \\ nil) and fetch_at(wam, index)

  :a = WAM.at(wam, 0)
  {:ok, :a} = WAM.fetch_at(wam, 0)
  {:error, :invalid_index} = WAM.fetch_at(wam, wam.size)
  

  Reach for these rather than passing an rng picked to defeat the alias — that trick depends on how probs is oriented and breaks silently when it changes.

Documentation can be generated with ExDoc and published on HexDocs. Once published, the docs can be found at https://hexdocs.pm/wam.