How can I quickly find unique list items?

I use the loop-every-single-list-item approach to filter out unique elements in a given list, which tends to be very inefficient way as a list grow in size, or as function call frequency increases. Lately I was working on event handling patch and needed fast method for filtering out unique function handlers in a callback lists which got to be run quite frequently.

I've put together couple of methods I often use, and quick performance tests for unsorted, ~1k size list scanned 1k times, and compared it against underscore.js's version (which performed quite badly, ~20x slower; probably because it's trying to accomplish too much in one go).

Is there a general, more efficient way to do this task?

var uniques = 

  // use named function to reference added .findindex() function inside
  function uniques (list) {

    for (

      var 

        // empty list to store unique items in
        uniqls = [], 

        it     = -1, 

        // aliases to speed up access
        length = list.length, 
        fi     = uniques.findindex;

      ++it < length;

      // if indexes are the same it's unique item
      // add the element to uniqls[]
      // (subtracting indexes here speeds up the function significantly)
      (fi(list, list[it]) - it) || uniqls.push(list[it]));

    return uniqls;
  };

// add .findindex() iterator member to .uniques()
Object.defineProperty(uniques, 'findindex' {

  // make it wide open
  'configurable': true, 
  'enumerable'  : true, 
  'writable'    : true, 

  'value'       : function (ls, node) {

    // loop until provided element is found 
    // skip 'update' and 'process' parts here, do just 'break test'
    // (basic `for ...` loop seems to perform well here)
    for (var it = -1, length = ls.length; (++it < length) && (node !== ls[it]););

    // if it hit list's end no such item exists in it
    // return default `-1` flag, or item's index (`it`)
    return (length - it) ? it : -1;
  }});

```
// this one is about ~2x slower the

If you can assume the collection is going to be large you can use ES6 Set

function uniques(array) {
   return [for (x of new Set(array)) x];
}

If the environment supports Array.from its just going to be Array.from(new Set(array))... beauty!

function uniques(array) {
   return Array.from(new Set(array));
}

Well thats how we would want to write it anyway... But alas, we live in tough times where people still try to support Chrome 33 and Firefox 26 (poor souls). I'll let you fellows in on the way some popular libraries write their uniq functions I suppose. Actually, I recently improved underscore's uniq function so you may notice its faster than you expect. Lodash's method is even faster in some cases

Anyway, heres the fastest way I know how to make a set, there was some discussion in doing it this way in underscore... It similar to what lodash does (here's a discussion on implementations https://github.com/CrossEye/ramda/issues/183#issuecomment-49565265)

function uniques(array) {
    var result = [], val, ridx;
    outer:
    for (var i = 0, length = array.length; i < length; i++) {
        val = array[i];
        ridx = result.length;
        while (ridx--) {
          if (val === result[ridx]) continue outer;
        }
        result.push(val);
    }
    return result;
}

Some key things to notice - see that its checking backwards, that will improve speed for near sorted collections. You can use indexOf instead of the while loop -- thats the difference between the lodash and underscore implementations.

You can write the while loop as below if ya prefer

while (ridx-- && val !== result[ridx]) {}
if (ridx !== -1) result.push(value);

JSPerf for your pleasure, removed the set unique but you can try it in Firefox

StackExchange Code Review Q#57581, answer score: 11