Binary Tree vs Linear Lookup

JavaScript performance comparison

Test case created by Josh Perry

Info

Compares the speed of looking up of a value from a flat list and from a binary tree.

Preparation code

<script src="//ajax.googleapis.com/ajax/libs/jquery/1/jquery.min.js">
</script>
<script>
Benchmark.prototype.setup = function() {
    function leftNode(nodeidx) {
      return (2 * nodeidx) + 1;
    }
   
    function rightNode(nodeidx) {
      return (2 * nodeidx) + 2;
    }
   
    function addValueToNode(tree, nodeidx, value) {
      var currentidx = nodeidx;
      while (true) {
        if (value > tree[currentidx]) {
          var right = rightNode(currentidx);
          if (!tree[right]) {
            tree[right] = value;
            break;
          } else currentidx = right;
        } else {
          var left = leftNode(currentidx);
          if (!tree[left]) {
            tree[left] = value;
            break;
          } else currentidx = left;
        }
      }
    }
   
    function addValueToTree(tree, value) {
      if (tree.length == 0) tree.push(value)
      else addValueToNode(tree, 0, value);
    }
   
    function addValuesToTree(tree, values) {
      for (var i = 0; i < values.length; i++)
      addValueToTree(tree, values[i]);
    }
   
    function addDictionaryToTree(tree, dict) {
      var values = [];
      for (var key in dict) {
        values.push(key);
      }
      values.sort();
      addValuesToTree(tree, values);
    }
   
    function inOrder(tree, nodeidx, func) {
      if (tree[nodeidx]) {
        //traverse the left subtree
        var leftidx = leftNode(nodeidx);
        var leftval = tree[leftidx];
        if (leftval !== null) {
          inOrder(tree, leftidx, func);
        }
   
        if (!func(tree[nodeidx])) return;
   
        var rightidx = leftNode(nodeidx);
        var rightval = tree[rightidx];
        //traverse the right subtree
        if (rightval !== null) {
          inOrder(tree, rightidx, func);
        }
      }
    }
   
    var tree = [];
    var values = [];
    for (var i = 0; i < 10000; i++) {
      var val = Math.random() * 1000
      while (values.indexOf(val) >= 0)
      val = Math.random() * 1000
   
      values.push(val);
    }
    addValuesToTree(tree, values);
   
    var lookupValues = [];
    for (var i = 0; i < 1000; i++) {
      var val = Math.random() * 1000
      while (lookupValues.indexOf(val) >= 0)
      val = Math.random() * 1000
   
      lookupValues.push(val);
    }
    var lookupLength = lookupValues.length;
   
   
    function findClosestValue(tree, nodeidx, needle) {
      var found = 0;
   
      inOrder(tree, nodeidx, function(nodeval) {
        if (nodeval < needle) {
          found = nodeval;
          return true;
        }
   
        return false;
      });
   
      return found;
    }
   
    function naiveFindClosestValue(haystack, needle) {
      var result;
   
      for (var key in haystack) {
        var dist = key - needle;
   
        if ((dist < 0 && dist < result) || result === undefined) {
          result = key;
        }
      }
   
      return result;
    }
   
    function rand(from, to) {
      return Math.floor(Math.random() * (to - from + 1) + from);
    }
};
</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
Linear Lookup
naiveFindClosestValue(values, lookupValues[rand(0, lookupLength - 1)]);
pending…
B-Tree Lookup
findClosestValue(tree, 0, lookupValues[rand(0, lookupLength - 1)]);
pending…

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

Compare results of other browsers

0 comments

Add a comment