Is there a non loop-every-single-list-item approach to find unique list items?

Question

I know I could use the loop-every-single-list-item approach to filter out unique elements in a given list, but I feel like there's probably a neat, quick way to do it.

How can I find unique list items in JavaScript, without looping through and filtering them manually?

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.

Here's what I'm trying to do:

  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;
  })();

Implementation:

// 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; 

  ls.unique()

);

Answer 1

No. If you have a list, you will need to look at least once at every single item to determine whether it is unique.

If you need something faster, don't use a list.

Btw, even on a list you can implement a unique-algorithm in less than the O(n²) that you currently have. See Easiest way to find duplicate values in a JavaScript array for some clever approaches.

I was working on event handling patch and needed fast method for filtering out unique function handlers in a callback list which got to be run quite frequently.

Then you don't want to put them in that list in the first place. Don't check the list for duplicates when you run it (which as you say is frequent), but when you insert a new handler.

If you think that using .indexOf to find a handler in the list is still too slow, you can mark every function object that it is already contained in the list. Choose a unique (per list) property name, and put a value on that property of each function that is in the list. You can then check in constant runtime for duplicates.

Answer 2

If you have a unique key, using a dictionary is a good option. However, if you have some logic that needs to be executed to perform your filtering, I'd go with UnderscoreJS. Check out the _.filter method. It's a great library with lots to offer in this area.

http://underscorejs.org/#filter

Answer 3

I don't think there is a way to get unique list of items without iterating through each item. If you're looking for a built-in library function, I don't think there is one in Angular.

It would be simple enough to create one:

function unique(array, fn) { 
   var hash = [];
   var list = [];
   for(var i = 0; i < array.length; ++i) {
        var key = fn(array[i]);
        if (key && !hash[key]) {
           list.push(array[i]);
           hash[key] = key;
        }
   }
   return list;
}

Usage:

var myList = [ { id:1, name="oranges"},
               { id:2, name="apples" },
               { id:1, name="oranges"},
               { id:3, name="pears" },
               { id:3, name="pears" } ];

var uniqueList = unique(myList, function(item) { return item.id; });