Unique Array Algorithm

JavaScript performance comparison

Test case created by Camilo Martin and last updated

Info

I've compiled this benchmark as research for my graphene selector engine, it's part of this wiki page.

There's unit tests in there. Since jQuery fails the tests I don't include $.unique here.

Preparation code

<script src="//underscorejs.org/underscore-min.js"></script>
<script>
// Polyfills

if (!Array.prototype.filter)
{
  Array.prototype.filter = function(fun /*, thisp*/)
  {
    "use strict";
 
    if (this == null)
      throw new TypeError();
 
    var t = Object(this);
    var len = t.length >>> 0;
    if (typeof fun != "function")
      throw new TypeError();
 
    var res = [];
    var thisp = arguments[1];
    for (var i = 0; i < len; i++)
    {
      if (i in t)
      {
        var val = t[i]; // in case fun mutates this
        if (fun.call(thisp, val, i, t))
          res.push(val);
      }
    }
 
    return res;
  };
}

if (!Array.prototype.indexOf)
{
  Array.prototype.indexOf = function(elt /*, from*/)
  {
    var len = this.length >>> 0;

    var from = Number(arguments[1]) || 0;
    from = (from < 0)
         ? Math.ceil(from)
         : Math.floor(from);
    if (from < 0)
      from += len;

    for (; from < len; from++)
    {
      if (from in this &&
          this[from] === elt)
        return from;
    }
    return -1;
  };
}

// Implementations

function uniqueByLoop (a) {
    var r = [];
    o:for(var i = 0, n = a.length; i < n; i++)
    {
        for(var x = 0, y = r.length; x < y; x++)
      {
        if(r[x]===a[i])
        {
          continue o;
        }
      }
      r[r.length] = a[i];
    }
    return r;
};

window.uniqueByFilter = function(a){return function(array){return array.filter(a)}}(function(a,b,c){return c.indexOf(a,b+1)<0});

function uniqueByFilterInline(array){return array.filter(function(a,b,c){return c.indexOf(a,b+1)<0})}

function arrayLastUnique(array) {
    return array.filter(function (a, b, c) {
        // keeps last occurrence
        return c.indexOf(a, b + 1) < 0;
    });
}

function arrayFirstUnique(array) {
    return array.filter(function (a, b, c) {
        // keeps first occurrence
        return c.indexOf(a) === b;
    });
}

function getUnique(a) {
  var b = [a[0]], i, j, tmp;
  for (i = 1; i < a.length; i++) {
    tmp = 1;
    for (j = 0; j < b.length; j++) {
      if (a[i] == b[j]) {
        tmp = 0;
        break;
      }
    }
    if (tmp) {
      b.push(a[i]);
    }
  }
  return b;
}

function inPlaceUnique(array) {
    var reindex = false, length = array.length;
    for (var i = 0; i < length; i++) {
        if (array.indexOf(array[i], i + 1) !== -1) {
            delete array[i];
            reindex = true;
        }
    }
    if (reindex) {
        var reindexed = [];
        var counter = 0;
        for (var i = 0; i < length; i++) {
            if (i in array) {
                reindexed[counter++] = array[i];
            }
        }
        array = reindexed;
    }
    return array;
}

function inPlaceSpliceUnique(array) {
    for (var i = 0, length = array.length; i < length; i++) {
        if (array.indexOf(array[i], i + 1) !== -1) {
            array.splice(i--, 1);
        }
    }
    return array;
}

// I like this one, even if it's not the fastest.
function bufferUnique(a) {
    var b = [], c = 0;
    for (var i = 0, n; n = a[i]; i++) {
        if (b.indexOf(n) === -1) {
            b[c++] = n;
        }
    }
    return b;
}
</script>
<script>
Benchmark.prototype.setup = function() {
    //var nodes = [].slice.call(document.getElementsByTagName('*'));
    // Goddamned IE
    for (var nodes = [], raw = document.getElementsByTagName('*'), len = raw.length, i = 0; i < len; i++) nodes[i] = raw[i];
   
    var nodesTwice = nodes.concat(nodes);
};
</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
uniqueByLoop
window.uniqued = uniqueByLoop(nodesTwice);
pending…
UnderscoreJS _.uniq
window.uniqued = _.uniq(nodesTwice);
pending…
uniqueByFilter
window.uniqued = uniqueByFilter(nodesTwice);
pending…
uniqueByFilterInline
window.uniqued = uniqueByFilterInline(nodesTwice);
pending…
arrayLastUnique
window.uniqued = arrayLastUnique(nodesTwice);
pending…
arrayFirstUnique
window.uniqued = arrayFirstUnique(nodesTwice);
pending…
getUnique
window.uniqued = getUnique(nodesTwice);
pending…
inPlaceUnique
window.uniqued = inPlaceUnique(nodesTwice);
pending…
inPlaceSpliceUnique
window.uniqued = inPlaceSpliceUnique(nodesTwice);
pending…
bufferUnique
window.uniqued = bufferUnique(nodesTwice);
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