binary search versus indexof versus hash key check

JavaScript performance comparison

Revision 3 of this test case created

Preparation code

<script src="//ajax.googleapis.com/ajax/libs/jquery/1/jquery.min.js"></script>
<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 lo = 0, hi = arr.length, check;
  while (true) {
    check = Math.floor(lo + ((hi - lo) / 2))
    //console.log("lo",lo,"hi",hi,"check",check,"val",arr[check])
    if (arr[check] === str) {
      return true
    }
    if (arr[check] < str) {
      lo = check
    } else {
      hi = check-1
    }
    if (hi === lo) {
      return false
    }
  }
}

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

var inHash = function(hash, str){
  return <script src="//www.cinsoft.net/mylib099-min.js"></script>
<script src="//ajax.googleapis.com/ajax/libs/prototype/1/prototype.js"></script>
!!hash[str];
}
</script>

Preparation code output

!!hash[str]; }

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…
jquery
assert($.inArray(props, goodkey), true);
assert($.inArray(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