How can I quickly find unique list items?

Question

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 then previous 
  // despite the fact it uses fancy 'ES5 magic'
  Array.prototype.unique = (function () {

    // main Array#unique method
    var uni = function uni () {
      return this.filter(uni.x);
    };

    // attach a helper for resolving unique elements
    // if element is at current position, not before, 
    // it's unique one, pass `true` flag to .filter()
    uni.x = function (node, pos, ls) {
      return pos === ls.indexOf(node);
    };

    // save
    return uniq;
  })();

---

// and underscore performed ~20x slower because all of that functionality built in
// (they should break the method down to couple of more specialized components)

// snippet from: 
// [underscore.js](https://github.com/jashkenas/underscore.git)
// Produce a duplicate-free version of the array. If the array has already
// been sorted, you have the option of using a faster algorithm.
// Aliased as `unique`.
_.uniq = _.unique = function(array, isSorted, iterator, context) {
  if (array == null) return [];
  if (_.isFunction(isSorted)) {
    context = iterator;
    iterator = isSorted;
    isSorted = false;
  }
  if (iterator) iterator = lookupIterator(iterator, context);
  var result = [];
  var seen = [];
  for (var i = 0, length = array.length; i < length; i++) {
    var value = array[i];
    if (isSorted) {
      if (!i || seen !== value) result.push(value);
      seen = value;
    } else if (iterator) {
      var computed = iterator(value, i, array);
      if (_.indexOf(seen, computed) < 0) {
        seen.push(computed);
        result.push(value);
      }
    } else if (_.indexOf(result, value) < 0) {
      result.push(value);
    }
  }
  return result;
};

---

//
//   and test all three functions:
// 
// sample list:
//   generate ~1K long list of integers:
//     get the keys of string object of length 32,
//     map every item to key-list itself, 
//     flatten, shuffle..
var ls = 
  Array.prototype.concat.apply([], 
    Object.keys(new String('1'.repeat(32)))).
  map(function (node, pos, list) { return list; }).
  sort(function () { return Math.random() < Math.random(); });

// run each function 1K times fetching unique values 
for (

  var 
    it   = -1, 
    l    = 1000, 

    // record iteration start
    tm   = Date.now();

  ++it < l; 


  // execute sequentualy: 
  uniques(ls)
  // ls.unique()
  // _.uniq(ls)
);

console.log(Date.now() - tm);
//
// 1. .uniques()          : 400 - 600 ms
// 2. Array#unique        : ~900ms
// 3. underscore _.uniq() : ~10s
//
// eof

Answer 1

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

Answer 2

There are some formatting issues here, but I'm going to focus on performance in my review, and others may come after me to touch on best practices with comments and formatting.

Try to avoid running the unique list item function often, as you say you are. Instead, see if you can run it when inserting new handlers to ensure that all handlers remain unique.

That's an idea, but it may not be possible for your situation, so lets have a look at the efficiency of your code, versus what I was able to put together after much research.

Performance:

Your method is the best that I could find on the web, well done. I did try one that I put together from related popular questions on Stack Overflow, and that's included in the code below (Third Method).

The following code includes 2 of your methods (Titled First Method & Second Method) and one of my own, with a much, much more accurate benchmarking strategy. The functions are run once against 10,000 item list of random whole numbers between 1 & 11, converted to strings.

Results First (10,000 item list):

M1 Unique 1,4,9,7,3,10,2,11,5,8,6
M1 loop: 3.000ms

M2 Unique 1,4,9,7,3,10,2,11,5,8,6
M2 loop: 7.000ms

M3 Unique 1,10,11,2,3,4,5,6,7,8,9
M3 loop: 10.000ms

And the code (See JSFiddle):

/* First Method - Yours */

var uniques = function uniques(list) {

    for (var uniqls = [],
    it = -1,
    length = list.length,
    fi = uniques.findindex;

    ++it < length;

    (fi(list, list[it]) - it) || uniqls.push(list[it]));

    return uniqls;
};

Object.defineProperty(uniques, 'findindex', {

    'configurable': true,
        'enumerable': true,
        'writable': true,
        'value': function (ls, node) {

        for (var it = -1, length = ls.length;
        (++it < length) && (node !== ls[it]););
        return (length - it) ? it : -1;

    }
});

/* Second Method - Yours */

Array.prototype.unique = (function () {

    var uni = function uni() {
        return this.filter(uni.x);
    };

    uni.x = function (node, pos, ls) {
        return pos === ls.indexOf(node);
    };

    return uni;

})();

/* Third Method - Mine */

function sortUnique(ls) {

    var sorted_arr = ls.sort();
    var results = [];
    for (var i = 0; i < ls.length; i++) {

        if (sorted_arr[i + 1] !== sorted_arr[i]) {

            results.push(sorted_arr[i]);

        }

    }

    return results;
}


/* Define List */

// Define list of 10,000 random whole numbers between 1 and 11

var ls = [];
for (var i = 0; i <= 10000; i++) {

    ls.push((Math.round((Math.random() * 10) + 1)).toString());

}

/*   Rather than the date() method you were using for benchmarks
 *   (which can be inaccurate for benchmarking), using console.time() 
 *   allows for extremely accurate benchmarking.
 */

console.log(ls);

console.time("M1 loop"); 

console.log("M1 Unique " + uniques(ls));

console.timeEnd("M1 loop");

console.time("M2 loop");

console.log("M2 Unique " + (ls.unique()));

console.timeEnd("M2 loop");

console.time("M3 loop");

console.log("M3 Unique " + (sortUnique(ls)));

console.timeEnd("M3 loop");

---

Update:

Megawac impressively does offer a method that is ~ over 2x faster. I had trouble implementing his Set() solution, however his representation of using a set works extremely fast. I would argue that there is no faster method in JavaScript.