Range Lookup

Benchmark created by Jonathan Skeate on December 1, 2014

Setup

var ranges = [];
    for( var i = 0; i < 10000; i++ ){
      var start = Math.random() * 1000000;
      var end = start + Math.random() * (1000000-start);
      ranges.push({start:start, end: end});
    }
    
    var sortedByStart = ranges.sort(function(range_a, range_b){
      return range_b.start - range_a.start;
    });
    sortedByStart.forEach(function(range, index){
      range.startIndex = index;
    });
    
    var sortedByEnd = ranges.sort(function(range_a, range_b){
      return range_b.end - range_a.end;
    });
    
    sortedByEnd.forEach(function(range, index){
      range.endIndex = index;
    });
    
    function findLowestHigher(value, list, property){
      low = 0;
      high = list.length;
      while( low < high ){
        var test = Math.floor(low + (high - low) / 2);
        if( list[test][property] > value ){ high = test; }
        else{ low = test + 1; }
      }
      return low;
    }
    
    function findStart(value){
      return findLowestHigher(value, sortedByStart, 'start');
    }
    
    // finds the index of the lowest end higher than value
    function findEnd(value){
      return findLowestHigher(value, sortedByEnd, 'end');
    }

Test runner

var value = Math.random() * 1000000;
var inRanges = [];
ranges.forEach(function(range){
  if( value >= range.start && value <= range.end ){
    inRanges.push(range);
  }
});

var value = Math.random() * 1000000;

var startedBeforeIndex = findStart(value);
var endedAfterIndex = findEnd(value);

var inRanges = sortedByStart
  .slice(0, startedBeforeIndex)
  .filter(function(range){
    return range.endIndex < endedAfterIndex;
  });

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.

• Revision 1: published by Jonathan Skeate on December 1, 2014