4 ms·
Walker's Alias Method for quickly sampling from an array
- chpatrick 12y agoOne of my lecturers at Imperial College called it the most beautiful unknown algorithm. :)
- willvarfar 12y agoDo they think Reservoir Sampling known then? ;)
- gknoy 12y agoThe 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-method-for-random-objects-with-diffe/ http://code.activestate.com/recipes/576564-walkers-alias-met...
- robrenaud 12y agoThere 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/ http://www.keithschwarz.com/darts-dice-coins/ And the corresponding HN discussion. https://news.ycombinator.com/item?id=3401510 https://news.ycombinator.com/item?id=3401510
- snogglethorpe 12y agoYeah that keithschwarz.com writeup is super readable and pleasant, with simple illustrations and figures that just leap out and practically explain everything themselves.... :]
- gwillen 12y agoI 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.