Optimize/Refactor Javascript Unique Array function

This is one idea of implementation:

Array.prototype.unique = function () {
  unique_array = [];
  for (var i = 0, l = this.length; i < l; i++) {
    if(unique_array.indexOf(this[i]) == -1){
      unique_array.push(this[i]);
    }
  }
  return unique_array;
 }

This version uses Object.keys which is a ECMAScript 5 only feature, as you can see on this website http://kangax.github.com/es5-compat-table/

Array.prototype.unique_e5 = function () {
  unique_object = {};
  for (var i = 0, l = this.length; i < l; i++) {
    unique_object[this[i]] = 1;
  }
  return Object.keys(unique_object);
}

And this is how is done in prototype.js
https://github.com/sstephenson/prototype/blob/master/src/prototype/lang/array.js

/**
   *  Array#uniq([sorted = false]) -> Array
   *  - sorted (Boolean): Whether the array has already been sorted. If `true`,
   *    a less-costly algorithm will be used.
   *
   *  Produces a duplicate-free version of an array. If no duplicates are
   *  found, the original array is returned.
   *
   *  On large arrays when `sorted` is `false`, this method has a potentially
   *  large performance cost.
   *
   *  ##### Examples
   *
   *      [1, 3, 2, 1].uniq();
   *      // -> [1, 2, 3]
   *
   *      ['A', 'a'].uniq();
   *      // -> ['A', 'a'] (because String comparison is case-sensitive)
  **/
  function uniq(sorted) {
    return this.inject([], function(array, value, index) {
      if (0 == index || (sorted ? array.last() != value : !array.include(value)))
        array.push(value);
      return array;
    });
  }

Also not that the prototype version uses the Prototype enumerable method include, which is:

``
/**
* Enumerable#include(object) -> Boolean
* - object (?): The object to look for.
*
* Determines whether a given object is in the enumerable or not,
* based on the ==` comparison operator (equality with implicit type
* conversion).
*
* ##### Examples
*
* $R(1, 15).include(10);

For me, I'd always avoid methods that require lots of includes to things get working - and in my mind, the more code used.. the slower things will be (unless some form of caching is used). Which is why I would opt for a simple JavaScript solution. Your idea will work, but I think this one is faster:

Array.prototype.unique = function () {
  var a = this, b = [], c, i = a.length;
  again: while ( i-- ) {
    c = a[i];
    k = i; while( k-- ){ if (a[k] == c){ continue again; } }
    b.unshift( a[i] );
  }
  return b;
}

There are probably other improvements that can be made, for example it might be faster to find a way to use .push() rather than .unshift().

I haven't tested the above excessively, but it seems to work in all my tests so far. The reason why it gets a speed increase is because it reduces the area it is checking each time; it is also using subtle other speed increases like a decrementing while loop (means there are less conditional statements to check on each iteration), and creating shortcut vars that cut down access time.

As proof here is a jsPerf... albeit only tested on my set-up so far ;)

http://jsperf.com/compare-array-unique-versions

side note: -- the downside to my method is that it will only include the last found occurance of a duplicate (not the first as your's will). So if that ordering is important to you, then you'll have to refactor the code.

revision: -- after a few jsPerfs it seems clear that the while(i--) no longer holds a speed difference (at least not for FireFox 16 Mac OSX). Whilst on Chrome Mac OSX i--; seems slower than i++;

http://jsperf.com/compare-a-dec-while-against-a-for-loop

So taking in to account BillyBarry's comments the improved version should be:

Array.prototype.unique8 = function () {
  var a = this, b = [], c, i, l = a.length, j, k = 0;
  again: for ( i = 0; i < l; i++ ) {
    c = a[i];
    for ( j = 0; j < k; j++ ) { if (b[j] === c){ continue again; } }
    b[k++] = c;
  }
  return b;
}

Working from b, rather than a improves things quite a lot. Plus using k++; rather than .length for the internal loop makes quite a bit of difference for FireFox (Mac OSX) but has no affect on Chrome.

StackExchange Code Review Q#14741, answer score: 2