Generating weighted-probability lists in Javascript

js-weighted-list test page screenshot

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.

Advertisements
Leave a comment

3 Comments

  1. Nadir

     /  June 7, 2013

    This is exactly what I was looking for, Thank you so much, just when I thought this problem would takes weeks to figure out, I find this.

    Reply
  2. Michael

     /  March 3, 2016

    This is exactly what I was looking for, thanks for sharing.

    Reply
  1. Javascript unit testing « Tim Gilbert's Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: