I’ve made a good deal of progress on my Google App Engine application, about which more later. During the course of it, I started to keenly feel the need for a weighted random list. That is, I have a list and want to select a random sample from it, but it has an unequal (weighted) probability distribution; I want some of the items to be selected more frequently than others. I also need to modify the weights depending on what else is going on in the program (eg, in response to user input or web service results. Also, this is all happening on the front-end, so it needs to work in javascript.
Poking around for a while I couldn’t find anything obviously relevant to this, but I did find a pretty good breakdown of the problem and the algorithm to follow in this Stack Overflow answer. This implementation makes use of a heap in order to enable a binary search on the probability space. While digging through to understand it, I wound up reimplementing the thing in Javascript, and then made a bunch of improvements to the API for it. It’s pretty basic and doesn’t have any particular dependencies, so I’m releasing it as its own library, js-weighted-list.
It is available on github under the MIT license. There are still several things I need to improve with it, in particular it’s severely under-tested, but it’s decently documented and immediately usable for what I need it to do.
1 Comment