Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.javascript > #24437

Re: Difference between two arrays

Show all headers | View raw

On Monday, May 26, 2014 9:55:03 PM UTC-4, Andrew Poulos wrote:
> If I have two "simple" arrays and I need to create a third array of 
> 
> elements that are only in one of the arrays. I found this
> 
> 
> 
> Array.prototype.difference = function (a) {
> 
>    return this.filter(function (i) {
> 
>      return !(a.indexOf(i) > -1);
> 
>    });
> 
> };
> 
> 
> 
> which I don't fully understand but the issue with it that I have is that 
> 
> I need to run it on both arrays to get all the differences. For example
> 
> 
> 
> var arrX = [1, 2, 4, 6, 8],
> 
>      arrY = [4, 8, 9];
> 
> 
> 
> var arrRes1 = arrX.difference(arrY)); // 1,2,6
> 
> var arrRes2 = arrY.difference(arrX)); // 9
> 
> 
> 
> var arrRes = arrRes1.concat(arrRes2); // 1,2,6,9
> 
> 
> 
> Andrew Poulos

If your code is doing this often and the arrays have more than just a few 
elements then you might run into performance issues. I think that .indexOf
just implements a linear search hence the code you show is O(mn) where m, n are 
the lengths of the arrays (so roughly 1,000,000 comparisons if m = n = 1000). 
It might be better to first sort the arrays and then replace .indexOf with a
binary search function (giving you something like O((m+n)(log(m) + log(n))). 
For things like m = n = 1000 this would be an order of magnitude quicker. On 
the other hand, for small m and n the time spent sorting might be hard to 
justify.

If you are using these arrays as sets and they have the property that each
element occurs exactly once in each array, a slick approach would be to 
concatenate the two arrays then sort the result something like 

var arrZ = arrX.concat(arrY);
arrZ.sort()

then -- elements in the symmetric difference of arrX and arrY will be 
elements of arrZ with the property that they occur only once. Something like

//untested!
var arrW = new Array();
var i = 0;
while (i < arrZ.length - 1)
{
    if(arrZ[i] === arrZ[i+1])
    {
       i += 2; //skip over the duplicate
    }
    else
    {
      arrW.push(arrZ[i]);
      i++;
    }
}

This won't work if arrX and/or arrY already contain duplicates though in 
that case you could sort and remove duplicated before using the above code.

Back to comp.lang.javascript | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Difference between two arrays Andrew Poulos <ap_prog@hotmail.com> - 2014-05-27 11:55 +1000
  Re: Difference between two arrays Denis McMahon <denismfmcmahon@gmail.com> - 2014-05-27 05:58 +0000
  Re: Difference between two arrays John C <rescattered@gmail.com> - 2014-05-27 03:34 -0700
    Re: Difference between two arrays Spamless <Spamless@Nil.nil> - 2014-05-31 06:35 -0500
      Re: Difference between two arrays Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2014-05-31 14:57 +0200
        Re: Difference between two arrays Spamless <Spamless@Nil.nil> - 2014-06-01 03:43 -0500
          Re: Difference between two arrays Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2014-06-01 14:01 +0200
            Re: Difference between two arrays Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2014-06-01 16:53 +0200
  Re: Difference between two arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-05-27 13:41 +0100
    Re: Difference between two arrays Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2014-05-27 17:41 +0200
    Re: Difference between two arrays Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2014-05-27 17:49 +0200
      Re: Difference between two arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-05-27 17:34 +0100
        Re: Difference between two arrays Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2014-05-27 19:33 +0200
          Re: Difference between two arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-05-27 20:03 +0100
    Re: Difference between two arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-05-27 17:16 +0100
      Re: Difference between two arrays Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2014-05-27 19:29 +0200
  Re: Difference between two arrays Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2014-05-27 17:21 +0200
  Re: Difference between two arrays Dr J R Stockton <reply1400@merlyn.demon.co.uk.invalid> - 2014-05-28 18:22 +0100
    Re: Difference between two arrays Dr J R Stockton <reply1400@merlyn.demon.co.uk.invalid> - 2014-05-30 22:23 +0100
    Re: Difference between two arrays "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2014-05-31 14:59 -0700
      Re: Difference between two arrays "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2014-06-01 00:50 +0200
        Re: Difference between two arrays "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2014-05-31 16:17 -0700
          Re: Difference between two arrays "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2014-06-01 10:49 +0200
            Re: Difference between two arrays "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2014-06-01 13:37 -0700
      Re: Difference between two arrays Dr J R Stockton <reply1400@merlyn.demon.co.uk.invalid> - 2014-06-01 18:56 +0100

csiph-web