array-roadrunner-sepia

Fast Algorithm To Find Unique Items in JavaScript Array

When I had the requirement to remove duplicate items from a very large array, I found out that the classic method to be not optimized as it took a pretty long time than desired. So, I devised this new algorithm that can sort a large array in a fraction of the original time.

The fastest method to find unique items in array

This method is kind of cheeky in its implementation. It uses the JavaScript’s object to add every item in the array as key. As we all know, objects accepts only unique keys and sure we did capitalize on that.

Some Thoughts On This Algorithm

This is somewhat classified as “Hash Sieving” method and can also be related to a somewhat modified “Hash Sorting Algorithm” where every item in the array is a hash value and a hash function inserts item into a bucket, replacing existing values in case of hash collision. As such, this can be applied to any programming language for faster sieving of very large arrays.

This algorithm has a linear time complexity of O(2n) in worst case scenario. This is way better than what we will observe for the classic method as described below.

About the classic method

The classic (and most popular) method of finding unique items in an array runs two loops in a nested order to compare each element with rest of the elements. Consequently, the time complexity of the classic method to find the unique items in an array is around quadratic O(n²).

This is not a good thing when you have to find unique items within array of 10,000 items.

Comparing the above two algorithms

Test Data: An array of elements having N random integers.

Sample (N)Average CaseBest Case
ClassicNewClassicNew
500.430.250.010.02
1000.600.300.090.16
5009.570.870.10.2
100024.441.510.210.31
5000584.287.740.41.0
100002360.9015.030.71.8

Conclusion

This method of finding unique items within an array seems to be particularly useful for large arrays that are tending towards the real-life situations. When there are more items in an array that are similar, there is not much of a difference in performance and in fact, the classic algorithm scores better by a small margin. However, as the array gets more random, the runtime of the classic algorithm increases manifold.

  • Andy L

    You work wonders at times. This is such a simple trick and yet so effective. Perhaps no one thinks about performance and perfection of algorithms as much as you do!
    By the way, in line 3 of your Hash Seiving algorithm, why did you do o[this[i]] = this[i];?

    • http://www.shamasis.net/ Shamasis Bhattacharya

      Do not flatter me that much! :P

      o[this[i]] = this[i]; preserves the data-type of the items within the JavScript array. This is because JavaScript object keys are always string and we would not want to needlessly convert a numeric array to string array! By the way, if you are not bothered about the data-type of the unique array, then you can use a modified version of the algorithm that always returns string data-type and is faster due to lesser overhead.

      Array.prototype.strUnique = function() {
      var o = {}, i, l = this.length, r = [];
      for(i=0; i<l;i++) o[this[i]] = null;
      for(i in o) r.push(i);
      return r;
      };

  • http://www.javascriptbank.com/ JavascriptBank

    Very cool & good tip, thank you very much for sharing.
    Can I share this snippet on my http://www.javascriptbank.com/

    Awaiting your response. Thanks

    • http://www.shamasis.net/ Shamasis Bhattacharya

      Sure. Sharing is caring! Care back for me by retaining my link and attribution. :)

  • Kevin N

    I’m trying to use this (the modified string data-type only function) inside an embedded js tool (i believe it uses rhino) and I’m having difficulty.  Instead of removing the duplicates  I want to append  1, 2, 3…n at the end of the duplicative strings  (space then integer so Kevin,Kevin becomes  Kevin,Kevin 1). I’m new to js in general and not sure i’m creating the array correctly – I may ask some stupid questions.
    var urlarray = new Array(URLName.getString());
    should that work? – as I understand it from there I can call this function using the array?

    • http://www.shamasis.net/ Shamasis Bhattacharya

      Kevin,

      For your use of prefixing the duplicates within a JavaScript Array with number, the following code would be useful:

      Array.prototype.markDuplicates = function() {
      var o = {}, i, l = this.length, r = [];
      for(i=0; i<l; i += 1) {
      if(o[this[i]] >= 0) {
      o[this[i]] += 1;
      r.push(this[i] + ' ' + o[this[i]]);
      }
      else {
      o[this[i]] = 0;
      r.push(this[i]);
      }
      }
      return r;
      };

      // Usage would look like
      var myArr = ['Kevin', 'Kevin', 'Shamasis', 'Kevin'],
      newArr = myArr.markDuplicates();

  • Nilton

    reverse for loops are faster for spidermonkey.
    As for Kevin’s question:
    Array.prototype.toUnique = function() {
    var o = {}, i, l = this.length, r = []; n = []; modified=0;
    for(i=this.length-1; i>=0;–i){
    if(n[this[i]]){
    modified=1;
    o[this[i]+” “+ n[this[i]]] = this[i]+ n[this[i]]++;
    }else{
    o[this[i]] = this[i];n[this[i]]=1
    }
    }
    if(!modified)return this;
    for(i in o) r.push(o[i]);
    return r;
    };

    • http://www.shamasis.net/ Shamasis Bhattacharya

      I did not want to do a reverse so as to maintain the original order.

      • Relic

        Then ya just need to use .unshift() instead of .push()…. problem solved!

        • http://www.shamasis.net Shamasis Bhattacharya

          It was actually very stupid on my part to think in this direction! The fastest algo actually does not take into account array order. We could simply do the negative looping here.

          • Neumonicom

            That will only work for values that are object literals.  It will not work for objects, as their internal .toString() method will convert them to something like :[object Object].  Thus if you have multiple objects with the same constructor you will continually overwrite the last one.

          • Neumonicom

            Sorry, I meant primitives instead of object literals in the first line.  ’a 1 0 2′.

          • Neumonicom

            This is probably the fastest and most reliable way to create a unique array whose members can be of any object.  The only downside is that it will sort the results.  Perhaps there is a workaround?

            Array.prototype.unique = function(){
            this.sort(function(a,b){
            if(a===b)return 0;
            return 1;

            });
            var length = this.length;
            while(length–)if(this[length] === this[length-1])this.splice(length,1);
            return this;

          • http://www.shamasis.net Shamasis Bhattacharya

            This will fail on Google Chrome on arrays with many items. The WebKit insertion sort is not stable for equality sort. :(

  • http://joshuakalis.com Joshua Kalis

    I don’t like augmenting the default types much, so I just made a function.

    function (ar) {
    var f = {},
    i = 0,
    l = ar.length,
    r = [];
    while (i < l) {
    !f[ar[i]] && r.push(ar[i]);
    f[ar[i++]] = 1;
    }
    return r;
    };

    I have it as a method on a properly name-spaced object and use like this:

    var result = Utils.array.unique(array_name);

  • Trav

    Hi,

    warning… js novice.

    I have a js array with 50,000 objects in it.  I need to find unique object fields in the array.

    eg.

    var data = [{name: 'tom',age:12},{name:'sam',age:13},{name:'tom',age:20}];

    so i need to find unique base on object field like:

    var return = data.unique(‘name’);

    so return would now have:

    return = [{name: 'tom'},{name:'sam'}];

    I have this working using jquery.inArray but it is very slow with large data sets.

    Can you help me?

  • Nemoniccom

    I’m not so sure this is the best method. What about doing the following:

    Array.prototype.unique = function(){
    Var Len = this.length,
    Elems = [],
    Elemslen = 0′
    Table ={},
    I;
    For(I=0;I+<Len;I++){
    If(!Table[I]){
    Table[I] = 1;
    This[Elemslen++] = This[I];

    }
    }

    This.length = Elemslen;
    }

    • http://www.spencernetdevelopment.com/ Neumoniccom

      Sorry,  I tried to type this originally on an Ipad.  What a pain!  The code should be as follows:

      Array.prototype.unique = function(){
      var len = this.length,
      elems = [],
      elemsLen = 0,
      table ={},
      i;
      for(i=0;i<len;i++){
      if(!table[this[i]]){
      table[this[i]] = 1;
      this[elemsLen++] = this[i];
      }
      }

      this.length = elemsLen;
      return this;
      }

  • Izayoi400

    what i use:

    var arr1=[1,2,3,2,5,1,2,1,2,3,6,1,2,1,2,3]
    var blah=”"for(each1 in arr1) { if(blah.search(arr1[each1]) == -1 )  {  blah=blah+arr1[each1]  } }
    alert(blah)var newblah = blah.split(“”)alert(newblah)

  • Izayoi400

    sorry hopefully this will be formatted better…

    var arr1=[1,2,3,2,5,1,2,1,2,3,6,1,2,1,2,3]var blah=”"for(each1 in arr1){if(blah.search(arr1[each1]) == -1 ){blah=blah+arr1[each1]}}alert(blah)var newblah = blah.split(“”)alert(newblah)

    • http://www.spencernetdevelopment.com/ Neumoniccom

      This isn’t a very good method.  You should never use the for in loop for arrays.  That loop should only be used on objects where the number of properties / methods isn’t known ( idea taken from Nicolas C. Zakas’ Book “High Performance Javascript” p 62 – 63).  You decrease performance using the for-in loop because you have to access all the properties / members of the object and it’s prototype chain.

      Also note that using multiple object methods (IE split , search, etc.) will lead to performance degradation.This is what I was originally trying to post.  For string and numeric values I believe it is the most straight forward:By using the below prototype method you can call unique on any array object like this:var a = [4,5,4,3,45,3,12,1,234,5,4,3,2,1];a.unique();Here is the prototype method for the Array object:Array.prototype.unique = function(){  var len = this.length,         elems = [],         elemsLen = 0,         table ={},         i;  for(i=0;i<len;i++){    if(!table[this[i]]){      table[this[i]] = 1;      this[elemsLen++] = this[i];    }  }  this.length = elemsLen;  return this;}

  • Pingback: Fast Algorithm To Find Unique Items in JavaScript Array | Robin Jakobsson

  • http://twitter.com/vikasrao vikasrao

    I had the same need and came up with this solution a while ago, good to know it actually has a name :-) : http://vikasrao.wordpress.com/2011/06/09/removing-duplicates-from-a-javascript-object-array/

  • Msitchen

    This should be done with a hash table for O(n) 

  • Gregor

    Thanks for teaching me the term “Hash Sieving” I’ve been using this trick for 15 years but didn’t know it had a name.

    • http://www.shamasis.net/ Shamasis Bhattacharya

      You are right, we have used this technique for centuries now! However, for JS it is performance enhancing unlike many other languages. The overhead of dictionaries and other similar structures in many languages are comparatively higher.

      Agree?

  • Brandon Benvie

    Array.prototype.unique = function(){
    return this.filter(function(s, i, a){ return i == a.lastIndexOf(s); });
    }

    You loop through the array at most an average of 50% of the length of the array per item, when there’s zero doubles. The more items filtered the more efficient it is. Usually doesn’t beat the hash method but it has its place. It wins on style points though cause sometimes looking pretty is better than being smart.

    • http://www.shamasis.net Shamasis Bhattacharya

      Yeah! I always tend to have a fascination towards the “coolKid” variants. Sadly, the overhead of an in-loop function call scares me. :-/

  • Aurelio Jargas

    Thanks for the post!

    Just note that the two codes you posted are not 100% similar. The fastest version will consider 1 and “1″ equal, removing one of them. The classic keeps both in output.

    • http://www.shamasis.net Shamasis Bhattacharya

      You are correct in noting that. :) In fact, to retain data-type, it becomes a bit more complex where we can create a hash for each type. Then again, we will loose the original array item order. To retain the order, the amount of computation required will defeat the whole purpose of this method! :(

      • SlightlyTooKeen

        Just posted a solution to that one in a different comment – my solution had three passes in it, so was indeed slower.

        First, you find a unique string key that is not present in any objects in your array. This is O(N) – you’ll almost always guess a unique key first time, but you run through the array to double-check this.

        Second, you use the hash sieving method to filter your array. However, the key you use for the hash depends on the type of the item. For objects, you use the unique key from the first pass to generate an identifier for that object, so you know if you see that object again.

        The third pass is simply to remove that unique key from any objects.

        So, it’s slower than your solution, but it can handle objects.

    • Neumonicom

      Consider this variation as well.  This will preserve any data type without sorting the results.  Try running some tests on this to see if its faster.  One thing worth noting here is that native methods have been optimized, so avoiding as much conditional logic and loops as possible is a good thing:

      Array.prototype.unique = function(){
      var len = this.length,
      a = [],
      item,
      i=0;

      for(;i<len;){
      item = this[i++];
      if(a.indexOf(item) === -1)a.push(item);

      }
      return a;

  • Pingback: Fast Algorithm To Find Unique Items in JavaScript Array | x443

  • Pingback: JavaScript unique method for array prototype | t1u

  • skrat

    Nice, problem with all unique implementations I’ve seen is that they rely on toString instead of allowing a custom comparison function.

    • http://www.shamasis.net Shamasis Bhattacharya

      That’s true. The provision of delegating a comparator function would have been super (acknowledging the fact for the call overhead).

      • skrat

        My implementation for completeness, I wonder how the performance compares. http://pastie.org/4902499

        • http://www.shamasis.net Shamasis Bhattacharya

          Even before performance, I assume that you are not putting cross-browser limitations as a concern. Right?

          • skrat

            That’s right, I don’t care for IE < 9, in other words, the way to handle this is shims.

  • SlightlyTooKeen

    Seeing as your algorithm doesn’t work for arrays of objects (or distinguish between “1″ and 1):

    • SlightlyTooKeen

      Ooh – improvement for the middle section. Shorter, and probably faster:

  • Vince

    Your algorithm can be improved in case of no duplicates, using Brandon’s way, just adding after the line

    var a = [], l = this.length;

    the following lines

    var distinctItems = Object.keys(this.reduce(function (r, v) { return r[v] = 1, r; }, {})).length;

    if (distinctItems == l)
    return array;

    ;)

  • PowerProgram

    Hi Shamasis,

    Your work is really wonderful.

    Can you give me any fast ascending sort algorithm for the array of objects compare to classic algorithm.

    I don’t want to use the array.sort(), as my browser is old and generating various errors.

    Classic Algorithm is this, which is very slow for 50K+ array.

    function()
    {
    var l = this.length; temp;
    for(var i=0; i<l; i++)
    {
    for(var j=i+1; j Number(this[j].obj))
    {
    temp= this[j];
    this[j]= this[i];
    this[i] = temp;
    }
    }
    }
    return this;
    }

    I want to know if there is any other fast way we can sort this in asc order.

    Thanks in advance :)

    • http://www.shamasis.net Shamasis Bhattacharya

      You’ll speed me up if you can tell me if there is a specific pattern/nature of the array being sorted. Also, would help if you can convert it to pure JS. Also, what browser subset are we talking about? I’m not as expert as you say :-)

      • PowerProgram

        I am actually sorting the array with one of the object of the element of array in ascending order. My array is around 60K elements.

        We are using IE6, In this if we use default array.sort() to sort the array of objects of 60 K elements in it, it will give “Number Expected” error. If I use small array around 100 elements it will work fine. So I cannot use this for my big array. Some bug in old IE, they fixed in new IE versions

        My array is like
        this =[{X : 8, Y:2, Z:1}, {X:2,Y:1,Z:4},....]

        So if I want to sort this array based on X value in ascending order, I use the classic method which is slow for 60K elements array.

        Classic Method:

        function()
        {
        var l = this.length; temp;
        for(var i=0; i<l; i++)
        for(var j=i+1; j Number(this[j].X))
        temp= this[j];
        this[j]= this[i];
        this[i] = temp;
        return this;
        }

        I want to if there is any speed way to do this like the example you made for unique sort.

        • PowerProgram

          Some how my program is messed up after I pasted in my previous reply, so I am taking image and uploading for better understanding. Sorry for the inconvenience.

          My Classic Method:

    • http://geekyogi.com/ Om Shankar

      // Array.sort uses modified quick sort algorithm in Chrome, and should be therefore the fastest
      // In older browsers too, it will be faster than any devised method.

      yourArray.sort(function(a, b) {
      var textA = a.desirdeKey.toUpperCase();
      var textB = b.desirdeKey.toUpperCase();
      return (textA textB) ? 1 : 0;
      });

  • http://geekyogi.com/ Om Shankar

    Sir, you did not devise this method. This technique exists since ages (before 2009 ofcourse).
    Also, it can be done in a single for loop. I don’t understand why are you using an extra loop to push items.

    • http://www.shamasis.net Shamasis Bhattacharya

      First, drop the sir. :-) Half the programming techniques existed even prior to the days of Herman Hollerith – we simply re-apply and re-invent – and on some rare occasions, re-discover. As we speak, typing from our bedrooms seems so natural when it wasn’t as such a couple of decades back.

      Right now, making thousands of function calls on arrays seem trivial when at one point of time IE 5.1 used to run on a 32MB RAM desktop and as such, some still care for the resources they consume.

      Regarding the second loop, I think that is plain and genius strike of stupidity from my end! :-) But in retrospect, I do see the positives -

      1. In a bid to keep the original array immutable, the 2nd loop ensures that only the latest of the duplicates have been pushed in. How else would you ensure you push in the latest of duplicates?

      2. Also, back in those days, function call, even Array.push, was expensive and as such statistically expecting a lesser number of items for unique ensured that we do not needlessly push or even perform logical operation during the first loop.