Fast Algorithm To Find Unique Items in JavaScript Array

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];?

Do not flatter me that much!

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

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

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

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?

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

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

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

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

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?

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

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

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)

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)

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

[...] Fast Algo­rithm To Find Unique Items in JavaScript Array. via @LeaVerou This entry was posted in Web development and tagged algorithm, javascript by Robin. Bookmark the permalink. /* [...]

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/

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

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.

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?

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

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.