random
modulecrypto
modulerandom
for the examplesuniform()
returns a float0.0 ≤ X < 1.0
X < 0.5
○ (heads), X < 0.5
● (tails), X ≥ 0.5
uniform(N)
returns an integer 1 ≤ X ≤ N
uniform()
uniform(N) >
1 + trunc(N * uniform()).
choose(L) >
Nth = random:uniform(length(L))  1,
{H, [Choice  T]} = lists:split(Nth, L),
{Choice, H ++ T}.
%% {sum(Weight), [{Key, Weight}, …]}
wselect(N, {Sum, Pairs}) when N =< Sum >
wselect(N, {Sum, Pairs}, []).
wselect(N, L, {S, [H={K, W}  T]}, Acc) >
case N  W of
N1 when N1 > 0 >
wselect(N1, T, [H  Acc]);
_ >
{K, {S  W, lists:reverse(Acc, T)}}
end.
choose(L) >
Nth = random:uniform(length(L))  1,
lists:nth(Nth, L).
[a, a, a, b, c, d]
a
, ~16.6% b
, …{6, [ {a, 3}
, {b, 1}
, {c, 1}
, {d, 1} ]}
O(n)
memory, has O(1)
selection!O(n)
time (Vose)head  tail 

a 1  undefined 
b ⅔  a ⅓ 
c ⅔  a ⅓ 
d ⅔  a ⅓ 
O(n)
to updateO(n)
garbage, no sharing at allO(log n)
updatesO(log n)
garbage, good sharingO(n)
seeks, since sort is by keyO(n)
for every operationKey  Weight 

0  0 
Slides 

Source 

bob@redivi.com 

@etrepum 