Array unique (v6)

Revision 6 of this benchmark created by Peter on


Description

@wolframkriesing wondered what the most efficient unique function for Array would be: http://twitter.com/wolframkriesing/status/83847205189980160

Let’s find out!

Preparation HTML

<script src="//ajax.googleapis.com/ajax/libs/mootools/1.3/mootools-yui-compressed.js">
</script>
<script src="https://raw.github.com/mootools/mootools-more/master/Source/Types/Array.Extras.js">
</script>

Setup

var array = [],
      i;
  
  for (i = 0; i < 10000; ++i) array[i] = Math.random();
  
  function mootools_unique(arr) {
    var target = [];
    for (var i = 0, a = arr.length; i < a; i++) {
      var obj = arr[i];
      if (target.indexOf(obj) == -1) {
        target.push(obj);
      }
    }
    return target;
  }

  Benchmark.prototype.setup = function() {
    var mu = mootools_unique; // avoid scope lookup penalty in the test itself
  };

Test runner

Ready to run.

Testing in
TestOps/sec
Using indexOf - O(n2)
array.filter(function(element, index, array) {
  return array.slice(0, index).indexOf(element) == -1;
});
ready
Using indexOf and ~ - O(n2)
array.filter(function(element, index, array) {
  return !~array.slice(0, index).indexOf(element);
});
ready
Using a map - O(n)
array.filter(function() {
  var seen = {};
  return function(element, index, array) {
    return !(element in seen) && (seen[element] = 1);
  };
}());
ready
Using sort and filter - O((n lg n) + n)
array.sort().filter(function(element, index, array) {
  return element !== array[index - 1]
});
ready
Using better indexOf logic
array.filter(function(element, index, array) {
  return array.indexOf(element, index + 1) < 0;
});
ready
Using simpler in logic
array.filter(function(element, index, array) {
  return element in this ? false : this[element] = true;
}, {});
ready
Moo-More unique
array.unique();
ready
MooTools forEach inlined
mu(array);
ready

Revisions

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