9
\$\begingroup\$

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
\$\endgroup\$
12
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ An EMCAScript6 solution? It's not implemented in current browsers by default.. How is this a valid solution at this point? \$\endgroup\$ – Viziionary Jul 22 '14 at 3:03
  • \$\begingroup\$ Also, just checking: what size was the array that you ran this against with a 2ms benchmark? \$\endgroup\$ – Viziionary Jul 22 '14 at 3:27
  • 1
    \$\begingroup\$ You don't check all elements, you check all elements seen so far. I'm pretty sure it should be n sqrt(n) worst and O(n) for best case (sorted) \$\endgroup\$ – megawac Jul 23 '14 at 15:19
  • 1
    \$\begingroup\$ That is exactly what I said and what gives the formula I have given above. I just adapted your tests to the worst case that I have formulated: (2000 sorted) elements without any duplicates. Have a look here: jsperf.com/cr-57581/3 I would really like to discuss this in more depth but the comments are no place for that. Anyways, the worst case might not be of much interest but the average case and the best case might be. As to the average a deeper analysis would be necessary and the best case is "one element repeated over and over again" which is \$O(n)\$. \$\endgroup\$ – Nobody Jul 24 '14 at 8:06
  • 1
    \$\begingroup\$ More concise way: const uniques = arr => [...new Set(arr)]; \$\endgroup\$ – Przemek Jun 3 '18 at 20:47
7
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ nice one. It seems that performance test are 'necessary evil' in 'half-implemented' environments like JavaScript. In this case you have quite a few variables that can impact the performance, like: are you dealing with already sorted list, how many elements in the list are unique, how big the list is, browser engine in question, etc. And for each case you can resort to specialized, optimized, algorithm, but you generally can not know in advance what you got. In other languages this is already part of the language core, as @megawac suggests, where you simply do: a = set(mixedls) etc. \$\endgroup\$ – Nikola Vukovic Jul 22 '14 at 22:58
  • \$\begingroup\$ @nikolav right, my benchmark ran the functions against a 10,000 item unsorted array of random whole numbers (converted to strings) between 1 and 11. \$\endgroup\$ – Viziionary Jul 22 '14 at 23:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.