Weighted random in javaScript

Rejection sampling  is the first thing that comes to mind, whereby you build a lookup table with elements populated by their weight distribution, then pick a random location in the table and return it. As an implementation choice, I would make a higher order function which takes a spec and returns a function which returns values based on the distribution in the spec, this way you avoid having to build the table for each call. The downsides are that the algorithmic performance of building the table is linear by the number of items and there could potentially be a lot of memory usage for large specs (or those with members with very small or precise weights, e.g. {0:0.99999, 1:0.00001}). The upside is that picking a value has constant time, which might be desirable if performance is critical. 

 

Javascript Code:

function weightedRandom2(spec, paraName) {
    
    if(paraName == null) paraName = "value";
    
    var i, j, table=[];
    for (i in spec) {
    // The constant 10 below should be computed based on the
    // weights in the spec for a correct and optimal table size.
    // E.g. the spec {0:0.999, 1:0.001} will break this impl.
        for (j=0; j<spec[i][paraName]*100; j++) {
          table.push(spec[i]);
        }
    }
  
 return table[Math.floor(Math.random() * table.length)];
}

or there is another light-weighted way to do it:

function weightedRandom(array, param){
  var total = 0;
  
  if(param == null) param = "value";
  
  array.forEach(function(e){
    
    total += e[param];
    
  });
  
  // get random number
  
  max = array[0][param];
  random = randomRange(0, total);
  
  // calculate weighted random value
  
  selectedIndex = -1;
  
  for(i=0; i < array.length; i++) {
    
    if(random < max) {
      selectedIndex = i;
      break;
    } else if(i == array.length - 1){
      selectedIndex = array.length - 1;
      break;
    }
    max += array[i + 1][param];
  }
  
  if(selectedIndex != -1) {
    return array[selectedIndex];
  } else {
    return null;
  }
}


function randomRange(min, max) {
  return Math.random() * (max - min) + min;
}

 


Leave a comment

Your email address will not be published. Required fields are marked *