#!/usr/bin/env python
# This is a version of the Alias Method for weighted random selection
# that uses big and small indices instead of generators. It's not
# really faster, but it is more suitable to porting to languages like
# C that don't have generators.
#
# Copyright 2019 Bruce Hill.
# This code is released under the MIT license.
# For details, see: https://opensource.org/licenses/MIT
def prepare_aliased_randomizer(weights):
N = len(weights)
avg = sum(weights)/N
aliases = [(1, None)]*N
small_i = 0
while small_i < N and weights[small_i] >= avg:
small_i += 1
if small_i < N: # If all weights are the same, nothing to do
small = (small_i, weights[small_i]/avg)
big_i = 0
while big_i < N and weights[big_i] < avg:
big_i += 1
assert(big_i < N) # At least one weight is >= avg
big = (big_i, weights[big_i]/avg)
while big and small:
aliases[small[0]] = (small[1], big[0])
big = (big[0], big[1] - (1-small[1]))
if big[1] < 1:
small = big
big_i += 1
while big_i < N and weights[big_i] < avg:
big_i += 1
if big_i >= N: break
big = (big_i, weights[big_i]/avg)
else:
small_i += 1
while small_i < N and weights[small_i] >= avg:
small_i += 1
if small_i >= N: break
small = (small_i, weights[small_i]/avg)
def weighted_random():
r = random()*N
i = int(r)
odds, alias = aliases[i]
return alias if (r-i) > odds else i
return weighted_random