Array Comparison 1

JavaScript performance comparison

Revision 4 of this test case created

Preparation code

 
<script>
Benchmark.prototype.setup = function() {
    var a = [];
    var b = [];
    var arr = [];
    var obj = {};
    var max = 100000;
   
    for (var i = 0; i < max; i++) {
      if (i % 20) {
        b[max - i - 1] = arr;
        a[i] = arr;
      } else if (i % 10) {
        b[max - i - 1] = obj;
        a[i] = obj;
      } else {
        b[max - i - 1] = i;
        a[i] = i;
      }
    }
   
    function sameElementsBrunoLM(a, b) {
      // immediately discard if they are of different sizes
      if (a.length != b.length) return false;
   
      b = b.slice(0); // clone to keep original values after the function
      a.forEach(function(e) {
        var i;
        if ((i = b.indexOf(e)) != -1) b.splice(i, 1);
      });
   
      return !b.length;
    }
   
    function sameElementsBruno(a, b) {
   
      // if length is not the same then must not be equal
      if (a.length != b.length) return false;
   
      // do an initial sort which will group types
      a.sort();
      b.sort();
   
      for (var i = 0; i < a.length; i++) {
   
        // if primitive then comparison will do
        if (isPrimitive(a[i]) && isPrimitive(b[i])) {
   
          if (a[i] != b[i]) return false;
        }
        // if not primitive then we will need to check for obj ref
        else if (!isPrimitive(a[i]) && !isPrimitive(b[i])) {
          if (!a[i].__aCount) a[i].__aCount = 0;
          if (!b[i].__bCount) b[i].__bCount = 0;
          a[i].__aCount = a[i].__aCount + 1;
          b[i].__bCount = b[i].__bCount + 1;
        }
        // if both types are not the same then this array
        // contains different number of primitives
        else {
          return false;
        }
   
      }
      for (var i = 0; i < a.length; i++) {
        if (!isPrimitive(a[i])) {
          if (!a[i].__aCount) {
            return false;
          }
          if (!a[i].__bCount) {
            return false;
          }
          if (a[i].__aCount != a[i].__bCount) {
            return false;
          }
        }
      }
      // if it gets this far it must be the same
      return true;
    }
   
    function isPrimitive(arg) {
      var type = typeof arg;
      return arg == null || (type != "object" && type != "function");
    }
   
    function sameElementsHamidi(a, b) {
      if (a.length != b.length) {
        return false;
      }
      var ourB = b.concat();
      return a.every(function(item) {
        var index = ourB.indexOf(item);
        if (index < 0) {
          return false;
        } else {
          ourB.splice(index, 1);
          return true;
        }
      });
    }
   
    function sameElementsBergi(a) {
      var map, maps = [],
           // counting booleans, numbers and strings
          nulls = [],
           // counting undefined and null
          nans = [],
           // counting nans
          objs, counts, objects = [],
          al = arguments.length;
      // quick escapes:
      if (al < 2) return true;
      var l0 = a.length;
      if ([].slice.call(arguments).some(function(s) {
        return s.length != l0;
      })) return false;
   
      for (var i = 0; i < al; i++) {
        var multiset = arguments[i];
        maps.push(map = {}); // better: Object.create(null);
        objects.push({
          vals: objs = [],
          count: counts = []
        });
        nulls[i] = 0;
        nans[i] = 0;
        for (var j = 0; j < l0; j++) {
          var val = multiset[j];
          if (val !== val) nans[i]++;
          else if (val === null) nulls[i]++;
          else if (Object(val) === val) { // non-primitive
            var ind = objs.indexOf(val);
            if (ind > -1) counts[ind]++;
            else objs.push(val), counts.push(1);
          } else { // booleans, strings and numbers do compare together
            if (typeof val == "boolean") val = +val;
            if (val in map) map[val]++;
            else map[val] = 1;
          }
        }
      }
   
      // testing if nulls and nans are the same everywhere
      for (var i = 1; i < al; i++)
      if (nulls[i] != nulls[0] || nans[i] != nans[0]) return false;
   
      // testing if primitives were the same everywhere
      var map0 = maps[0];
      for (var el in map0)
      for (var i = 1; i < al; i++) {
        if (map0[el] !== maps[i][el]) return false;
        delete maps[i][el];
      }
      for (var i = 1; i < al; i++)
      for (var el in maps[i])
      return false;
   
      // testing of objects were the same everywhere
      var objs0 = objects[0].vals,
          ol = objs0.length;
      counts0 = objects[0].count;
      for (var i = 1; i < al; i++)
      if (objects[i].count.length != ol) return false;
      for (var i = 0; i < ol; i++)
      for (var j = 1; j < al; j++)
      if (objects[j].count[objects[j].vals.indexOf(objs0[i])] != counts0[i]) return false;
   
      // else, the multisets are equal:
      return true;
    }
   
    function mapTypes(a) {
   
      var _map = {};
   
      for (var i = 0; i < a.length; i++) {
   
        var _t = toType(a[i]);
        if (keyGen.hasOwnProperty(_t)) {
          _t = _t + keyGen[_t](a[i]);
        }
   
        if (!_map[_t]) {
          _map[_t] = [];
        }
   
        _map[_t].push(i);
      }
   
      return _map;
    }
   
    function mapTypesMatch(mapA, mapB) {
      var a = Object.keys(mapA);
      var b = Object.keys(mapB);
   
      if (a.length != b.length) return false;
   
      for (var i = 0; i < a.length; i++) {
   
        if (!mapB[a[i]]) return false;
        if (mapA[a[i]].length != mapB[a[i]].length) return false;
      }
   
      return true;
    }
   
   
    function arrayElementsMatch(mapA, sourceA, mapB, sourceB) {
   
      for (var key in mapA) {
        if (mapA.hasOwnProperty(key)) {
   
          for (var i = 0; i < mapA[key].length; i++) {
            var found = false;
            for (var k = 0; k < mapB[key].length; k++) {
              if (sourceA[mapA[key][i]] === sourceB[mapB[key][k]]) {
                mapB[key].slice(k, 1);
                found = true;
                break;
              }
            }
            if (!found) return false;
          }
        }
      }
   
      return true;
    }
   
   
    var keyGen = {
      "[object Object]": function(obj) {
        return Object.keys(obj).length;
      },
      "[object Array]": function(arr) {
        return arr.length;
      },
      "[object Date]": function(d) {
        return d.getYear();
      },
      "[object Number]": function(n) {
        return n.toString().length;
      },
      "[object String]": function(str) {
        return str.length;
      }
    }
   
    var toType = function(obj) {
        return Object.prototype.toString.call(obj);
        }
       
       
       
       
    function sameElementsBruno2(a, b) {
   
      if (a.length != b.length) return false;
   
      var mapA = mapTypes(a);
      var mapB = mapTypes(b);
   
      if (!mapTypesMatch(mapA, mapB)) return false;
      if (!arrayElementsMatch(mapA, a, mapB, b)) return false;
   
      return true;
    }
};
</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
BrunoLM
sameElementsBrunoLM(a, b);
pending…
Bruno
sameElementsBruno(a, b);
pending…
Hamidi
sameElementsHamidi(a, b)
pending…
Bergi
sameElementsBergi(a, b)
pending…
Bruno2
sameElementsBruno2(a, b);
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