binary search versus indexof versus hash key check

JavaScript performance comparison

Revision 4 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) {
  function binarySearch(a, value) {
    lo = 0;
    hi = a.length - 1;
    while (lo <= hi) {
        var mid = Math.floor((lo+hi)/2);
        if (a[mid] > value)
            hi = mid - 1;
        else if (a[mid] < value)
            lo = mid + 1;
        else
            return mid;
    }
    return null;
}

return binarySearch(arr, str)?true:false;
}

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

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

Preparation code output

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