Walker's Alias Method for quickly sampling from an array

There is a great article on engineering a whole bunch of increasingly good solutions the discrete random sampling problem.

http://www.keithschwarz.com/darts-dice-coins/

And the corresponding HN discussion.

https://news.ycombinator.com/item?id=3401510

Yeah that keithschwarz.com writeup is super readable and pleasant, with simple illustrations and figures that just leap out and practically explain everything themselves.... :]

The links to Python and Node versions were also helpful. The comments in the Python version [1] were especially helpful at explaining what was going on.

1: http://code.activestate.com/recipes/576564-walkers-alias-met...

I think the README mis-describes the performance comparison with the naive "huge array of samples" method.

In particular, both methods are O(1) after a precomputation step. What the Alias Method appears to get you is a significant reduction in space required.

One of my lecturers at Imperial College called it the most beautiful unknown algorithm. :)

Do they think Reservoir Sampling known then? ;)