• Global community
    • Language:
      • Deutsch
      • English
      • Español
      • Français
      • Português
  • 日本語コミュニティ
    Dedicated community for Japanese speakers
  • 한국 커뮤니티
    Dedicated community for Korean speakers
Exit
0

JS: How to remove duplicate items from an Array?

New Here ,
Nov 19, 2010 Nov 19, 2010

Copy link to clipboard

Copied

JS: How to remove duplicate items from an Array?

I guess there will be a simple way ...

TOPICS
Scripting

Views

22.1K

Translate

Translate

Report

Report
Community guidelines
Be kind and respectful, give credit to the original source of content, and search for duplicates before posting. Learn more
community guidelines

correct answers 1 Correct answer

Advisor , Nov 19, 2010 Nov 19, 2010

Hey!

Maybe something like this:

Array.prototype.unique = function (){
    var r = new Array();
    o:for(var i = 0, n = this.length; i < n; i++){
        for(var x = 0, y = r.length; x < y; x++){
            if(r==this) continue o;}
        r[r.length] = this;}
    return r;
}

Usage:

var myArray = ["a","b","c","c","a","d","b","b"];
alert(myArray.unique());

Hope that helps.

--

tomaxxi

http://indisnip.wordpress.com/

Votes

Translate

Translate
Advisor ,
Nov 19, 2010 Nov 19, 2010

Copy link to clipboard

Copied

Hey!

Maybe something like this:

Array.prototype.unique = function (){
    var r = new Array();
    o:for(var i = 0, n = this.length; i < n; i++){
        for(var x = 0, y = r.length; x < y; x++){
            if(r==this) continue o;}
        r[r.length] = this;}
    return r;
}

Usage:

var myArray = ["a","b","c","c","a","d","b","b"];
alert(myArray.unique());

Hope that helps.

--

tomaxxi

http://indisnip.wordpress.com/

Votes

Translate

Translate

Report

Report
Community guidelines
Be kind and respectful, give credit to the original source of content, and search for duplicates before posting. Learn more
community guidelines
LEGEND ,
Nov 19, 2010 Nov 19, 2010

Copy link to clipboard

Copied

I use Peter Kahrel's arrayCompress function for string arrays...

function arrayCompress(array){
    var str = array.sort().join('\r')+'\r';
    str = str.replace(/([^\r]+\r)(\1)+/g,'$1');

    str = str.replace(/\r$/,'');
    return str.split('\r');

}

Harbs

Votes

Translate

Translate

Report

Report
Community guidelines
Be kind and respectful, give credit to the original source of content, and search for duplicates before posting. Learn more
community guidelines
New Here ,
Nov 19, 2010 Nov 19, 2010

Copy link to clipboard

Copied

OK...

Very usefull funtions...!!!

THANKS...!!!

Votes

Translate

Translate

Report

Report
Community guidelines
Be kind and respectful, give credit to the original source of content, and search for duplicates before posting. Learn more
community guidelines
Guide ,
Nov 19, 2010 Nov 19, 2010

Copy link to clipboard

Copied

@Marijan

Your implementation is OK but it has a quadratic time complexity -- O(n²) -- because of the loop within the loop.

On large arrays (+1000 items), the "Hash Sieving” method is faster -- O(2n). Here is a functional implementation used for string arrays:

function unique(/*str[]*/ arr)
{
     var o={},
          r=[],
          n = arr.length,
          i;

     for( i=0 ; i<n ; ++i )
          o[arr] = null;

     for( i in o )
          r.push(i);

     return r;
}

// TEST:
alert( unique(["a","b","c","c","a","d","b","b"]) );
// => a, b, c, d

@Harbs

The arrayCompress function is very original, but I am skeptical about its performance on large arrays.

Also, there is two important issues to mention:

1) the original array is not preserved, because array.sort() reorders its own elements -- we can fix this using array.concat().sort().

2) the function does not work if any of the supplied strings already contains "\r".

@+

Marc

Votes

Translate

Translate

Report

Report
Community guidelines
Be kind and respectful, give credit to the original source of content, and search for duplicates before posting. Learn more
community guidelines
Advisor ,
Nov 19, 2010 Nov 19, 2010

Copy link to clipboard

Copied

Hey Marc!

Yes, I know that, and I already have your function,

but I didn't wanted to use it without your permission

--

tomaxxi

Votes

Translate

Translate

Report

Report
Community guidelines
Be kind and respectful, give credit to the original source of content, and search for duplicates before posting. Learn more
community guidelines
Guide ,
Nov 20, 2010 Nov 20, 2010

Copy link to clipboard

Copied

Marijan Tompa (tomaxxi) wrote:

Yes, I know that, and I already have your function,

but I didn't wanted to use it without your permission

I appreciate your scruples, but I really didn't invent anything:

http://www.google.com/search?q="Hash+Sieving"+JavaScript

Marc

Votes

Translate

Translate

Report

Report
Community guidelines
Be kind and respectful, give credit to the original source of content, and search for duplicates before posting. Learn more
community guidelines
LEGEND ,
Nov 20, 2010 Nov 20, 2010

Copy link to clipboard

Copied

Good points.

Nice function! I like the way it uses native features of Object to solve this problem...

It looks like the one you posted has an error. It creates null objects?

This looks like it's the correct (prototype) version. No?

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

Or function version:

function unique (array) {
   var o = {}, i, l = array.length, r = [];
   for(i=0; i<l;i++) o[array] = array;
   for(i in o) r.push(o);
   return r;
};

It might be possible to make this work on more types of objects by making this line something like this:

   for(i=0; i<l;i++) o[array.toString()] = array;

Harbs

Votes

Translate

Translate

Report

Report
Community guidelines
Be kind and respectful, give credit to the original source of content, and search for duplicates before posting. Learn more
community guidelines
LEGEND ,
Nov 20, 2010 Nov 20, 2010

Copy link to clipboard

Copied

Harbs. wrote:

It looks like the one you posted has an error. It creates null objects?

Ah nevermind. I didn't read your code well enough...

Votes

Translate

Translate

Report

Report
Community guidelines
Be kind and respectful, give credit to the original source of content, and search for duplicates before posting. Learn more
community guidelines
Guide ,
Nov 21, 2010 Nov 21, 2010

Copy link to clipboard

Copied

Harbs. wrote:

Harbs. wrote:

It looks like the one you posted has an error. It creates null objects?

Ah nevermind. I didn't read your code well enough...

* Provided that the function works on array of strings, we don't need to store the elements since they are strictly equal to the keys.

In this context, o[key]=null; is faster than o[key]=key;

* In you alternative code, you don't actually have to write:

o[array.toString()] = array;

Indeed, since o is a key-value object, the syntax o[xxx] expects a string and xxx will be converted into a string if necessary, which means that JS internally calls xxx.toString().

E.g.

var anything = {};
anything.toString = function(){return 'foo';};

var anyNumber = 3;

var obj = {};
obj[anything] = 'bar';  // i.e. obj['foo'] = 'bar'
obj[anyNumber] = 'baz'; // i.e. obj['3'] = 'baz'

alert( obj.toSource() );
// => {foo:"bar", 3:"baz"}

In conclusion, you can keep this syntax:

o[ array ] = array;

@+

Marc

Votes

Translate

Translate

Report

Report
Community guidelines
Be kind and respectful, give credit to the original source of content, and search for duplicates before posting. Learn more
community guidelines
LEGEND ,
Nov 21, 2010 Nov 21, 2010

Copy link to clipboard

Copied

  • Provided that the function works on array of strings, we don't need to store the elements since they are strictly equal to the keys.

In this context, o=null; is faster than o=key;

Yes. I realized that... Is the speed difference noticeable?

  • In you alternative code, you don't actually have to write:

o[array.toString()] = array;

Indeed, since o is a key-value object, the syntax o expects a string and xxx will be converted into a string if necessary, which means that JS internally calls xxx.toString().

True. I thought of editing my post but I figured I'll just leave it because toString() is clearer anyway (and possibly more efficient, but I forget those details easily)...

Harbs

Votes

Translate

Translate

Report

Report
Community guidelines
Be kind and respectful, give credit to the original source of content, and search for duplicates before posting. Learn more
community guidelines
Guide ,
Nov 21, 2010 Nov 21, 2010

Copy link to clipboard

Copied

LATEST

Harbs. wrote:

In this context, okey=null; is faster than okey=key;

Yes. I realized that... Is the speed difference noticeable?

Hmm, not really...

I've just performed an iterative rounds benchmark —in ExtendScript 3.92.114— with arrays of resp. 10,000 and 50,000 random strings. The unique() function using o[key]=null is only 1.1X faster than the same function using o[key]=arr. So the gap is absolutely not noticeable on small tables with hundreds of items.

Let's just say it's a better practice to nullify the values as there is no need to duplicate strings in the memory.

@+

Marc

Votes

Translate

Translate

Report

Report
Community guidelines
Be kind and respectful, give credit to the original source of content, and search for duplicates before posting. Learn more
community guidelines
Community Expert ,
Nov 20, 2010 Nov 20, 2010

Copy link to clipboard

Copied

Nice one, Marc.

Petr

Votes

Translate

Translate

Report

Report
Community guidelines
Be kind and respectful, give credit to the original source of content, and search for duplicates before posting. Learn more
community guidelines