Random Choice

(случайный выбор)

Bob Ippolito (@etrepum)

Erlang Factory Lite 2012, Moscow

Why this talk?

Andrey Andreyevich Markov

Андре́й Андре́евич Ма́рков

Markov chain

Markov text generator

Really?

Erlang's random module

Fair coin

Fair coin

X =

○ (heads), X < 0.5

● (tails), X ≥ 0.5

Die roll

Die roll

X =

Random selection without replacement

choose(L) ->
  Nth = random:uniform(length(L)),
  {H, [Choice | T]} = lists:split(Nth, L),
  {Choice, H ++ T}.

Random selection without replacement

Random selection without replacement

Selections =

 

L =

 

Weighted selection without replacement

Random selection with replacement

choose(L) ->
  lists:nth(random:uniform(length(L)), L).
    

Random selection with replacement

Selections =

 

L =

 

Weighted selection, naive

Weighted selection with replacement

Selections =

 

L =

 

Optimizing for memory

Alias method

Alias method

Die:

Coin:

headtail
a 1undefined
ba
ca
da

Handling updates

Using a tree

Simple max heap

Simple max heap


Key Weight

Questions?

Slides:
  etrepum.github.com/rndchoice_efl_2012

Code:
  github.com/etrepum/rndchoice_efl_2012

Twitter:
  @etrepum

/

#