Rekflwgn

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_a.start - range_b.start;
    }).slice();
    sortedByStart.forEach(function(range, index){
        range.startIndex = index;
    });
    
    var sortedByEnd = ranges.sort(function(range_a, range_b){
        return range_a.end - range_b.end;
    }).slice();
    
    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');
    }
    
    function findEnd(value){
        return findLowestHigher(value, sortedByEnd, 'end');
    }
    
    var valueToFind = Math.random() * 1000000;

Test runner

var inRangesLinear = [];
ranges.forEach(function(range){
  if( valueToFind >= range.start && valueToFind <= range.end ){
    inRangesLinear.push(range);
  }
});

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

var inRangesBinary = 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