binary search versus indexof versus hash key check

JavaScript performance comparison

Revision 5 of this test case created

Preparation code

<script>
//Big Array
var props = Array.prototype.slice.call(window.getComputedStyle(document.documentElement)).sort(),
    hash = {};

// random key, there are about 270
var goodkey = props[138], badkey = "I don't exist in the array";

props.forEach(function(v){
  hash[v] = true
});

var assert = function(val, expected){
  if(val !== expected){ throw new Error("Bad Assert"); }
}

var inArrayBinary = function(arr, str) {
  var minIndex = 0;
  var maxIndex = arr.length - 1;
  var currentIndex;
  var currentElement;

  while (minIndex <= maxIndex) {
      currentIndex = (minIndex + maxIndex) / 2 | 0;
      currentElement = arr[currentIndex];

      if (currentElement < str) {
          minIndex = currentIndex + 1;
      }
      else if (currentElement > str) {
          maxIndex = currentIndex - 1;
      }
      else {
          return true;
      }
  }

  return false;
}

var inArrayNativeIndexOf = function(arr, str){
  return !!~arr.indexOf(str);
}

var inHash = function(hash, str){
  return !!hash[str];
}
</script>

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in unknown unknown
Test Ops/sec
array.indexOf
assert(inArrayNativeIndexOf(props, goodkey), true);
assert(inArrayNativeIndexOf(props, badkey), false);
 
pending…
hash key check
assert(inHash(hash, goodkey), true);
assert(inHash(hash, badkey), false);
pending…
binary search
assert(inArrayBinary(props, goodkey), true);
assert(inArrayBinary(props, badkey), false);
pending…

Compare results of other browsers

Revisions

You can edit these tests or add even more tests to this page by appending /edit to the URL. Here’s a list of current revisions for this page:

0 comments

Add a comment