bruteforce versus bst versus hashtable versus binary search on sorted array

Benchmark created by zetlen on March 10, 2015

Setup

var size = 5000;
    var values = Array.apply(Array, Array(size));
    values.forEach(function(v, i) {
        values[i] = Math.floor(Math.random()*size/10);
    });
    
    
    // bruteforce
    
    function isSumPossibleBruteforce(values, target) {
      var addends = [],
          addend;
      for (var i = 0; i < values.length; i++) {
        addend = target - values[i]
        if (addends.indexOf(addend) !== -1) {
          return true;
        }
        addends.push(addend);
      }
      return false;
    }
    
    // bst
    
    
    function BinarySearchTree(value, left, right) {
      this.value = value;
      this.left = left;
      this.right = right;
    }
    
    var search = function(tree, value) {
      if (!tree || value === tree.value) return tree;
      if (value < tree.value) {
        return search(tree.left, value);
      } else {
        return search(tree.right, value);
      }
    }
    
    var append = function(tree, value) {
      if (tree.value === value) return tree;
      if (!tree.value) {
        tree.value = value;
      }
      if (value < tree.value) {
        if (tree.left) {
          return append(tree.left, value);
        } else {
          tree.left = new BinarySearchTree(value);
        }
      }
      if (value > tree.value) {
        if (tree.right) {
          return append(tree.right, value);
        } else {
          tree.right = new BinarySearchTree(value);
        }
      }
    }
    
    function isSumPossibleBST(values, target) {
      var addends = new BinarySearchTree(),
          addend;
      for (var i = 0; i < values.length; i++) {
        addend = target - values[i],
        node = search(addends, addend);
        if (node) {
          return true;
        }
        append(addends, addend);
      }
      return false;
    }
    
    // bruteforce
    
    function isSumPossibleHash(values, target) {
      var addends = {},
          addend;
      for (var i = 0; i < values.length; i++) {
        addend = (target - values[i]).toString();
        if (addends[addend]) {
          return true;
        }
        addends[addend] = true;
      }
      return false;
    }
    
    function binaryIsPresent(arr, searchElement) {
        'use strict';
     
        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 < searchElement) {
                minIndex = currentIndex + 1;
            }
            else if (currentElement > searchElement) {
                maxIndex = currentIndex - 1;
            }
            else {
                return true;
            }
        }
     
        return false;
    }
    
    
    var isSumPossibleSortedArray(values, target) {
      values = values.sort(function(a, b) {
        return a > b ? 1 : (a < b ? -1 : 0);
      });
      for (var s = 0; s < values.length; s++) {
        if (binaryIsPresent(values, target - values[i])) return true;
      }
      return false;
    }

Test runner

isSumPossibleBruteforce(values, Math.floor(Math.random()*size));

isSumPossibleBST(values, Math.floor(Math.random()*size));

isSumPossibleHash(values, Math.floor(Math.random()*size));

isSumPossibleSortedArray(values, Math.floor(Math.random()*size));

Revisions

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

• Revision 1: published by zetlen on March 10, 2015