# How to compute the difference between two arrays?

Discussion in 'Javascript' started by laredotornado, Dec 18, 2009.

Hi,

If I have two unsorted Javascript arrays, how do I compute the minus
operation? In other words, I have arrays A and B and I want to know A
- B, the elements in A that do not belong to B.

Thanks, - Dave

2. ### Evertjan.Guest

laredotornado wrote on 18 dec 2009 in comp.lang.javascript:

> If I have two unsorted Javascript arrays, how do I compute the minus
> operation? In other words, I have arrays A and B and I want to know A
> - B, the elements in A that do not belong to B.
>

You would have to define "do not belong to".
Never heard of that in this context.

Then you could describe how to do that on paper.

Then you do the same using javascript,
while trying to optimize the total time.

--
Evertjan.
The Netherlands.

Evertjan., Dec 18, 2009

3. ### Thomas 'PointedEars' LahnGuest

> If I have two unsorted Javascript arrays, how do I compute the minus
> operation? In other words, I have arrays A and B and I want to know A
> - B, the elements in A that do not belong to B.

You will not learn anything if you let your homework be done by others.

PointedEars
--
var bugRiddenCrashPronePieceOfJunk = (
navigator.userAgent.indexOf('MSIE 5') != -1
&& navigator.userAgent.indexOf('Mac') != -1
) // Plone, register_function.js:16

Thomas 'PointedEars' Lahn, Dec 18, 2009
4. ### Scott SauyetGuest

On Dec 18, 9:51 am, laredotornado <> wrote:
> If I have two unsorted Javascript arrays, how do I compute the minus
> operation?  In other words, I have arrays A and B and I want to know A
> - B, the elements in A that do not belong to B.

A good discussion on this is available here:

http://tinyurl.com/ybxulzy

Cheers,

-- Scott

Scott Sauyet, Dec 18, 2009
5. ### David MarkGuest

On Dec 18, 12:59 pm, Scott Sauyet <> wrote:
> On Dec 18, 9:51 am, laredotornado <> wrote:
>
> > If I have two unsorted Javascript arrays, how do I compute the minus
> > operation?  In other words, I have arrays A and B and I want to know A
> > - B, the elements in A that do not belong to B.

>
> A good discussion on this is available here:
>
>    http://tinyurl.com/ybxulzy
>

Depends on your definition of good. And I'm not sure it is the same
question as the array contents are specified to be numbers only,
despite some of the odd solutions that followed:-

minusAB : function (a, b) {
var h = {};
b.each(function (v) { h[v] = true; });
return a.filter(function (v) { return !h.hasOwnProperty(v); });
},

If the values are all numbers (and there are no missing properties):-

var m = [], r = [];

for (var i = b.length; i-- {
m[b] = true;
}
for (i = a.length; i-- { // Changes order
if (!m[a]) {
r.push(a);
}
}
return r;

If order matters, change the direction of the loops (or return
r.reverse()).

For sparsely populated arrays, for-in loops (with appropriate filters)
would be faster.

In any event, no magical "hash" spells are necessary for numbers.

David Mark, Dec 18, 2009
6. ### Thomas 'PointedEars' LahnGuest

David Mark wrote:

> Scott Sauyet wrote:
>> > If I have two unsorted Javascript arrays, how do I compute the minus
>> > operation? In other words, I have arrays A and B and I want to know A
>> > - B, the elements in A that do not belong to B.

>> A good discussion on this is available here:
>> http://tinyurl.com/ybxulzy

>
> Depends on your definition of good. And I'm not sure it is the same
> question as the array contents are specified to be numbers only,

It is the same question, however a bit vague, too. One would need to define
first whether, if A = [x, x] and B = [x], A - B would be [] or [x] as there
is an interpretation so that there was an `x in A' that `does not not to B'.

> despite some of the odd solutions that followed:-
>
> minusAB : function (a, b) {
> var h = {};
> b.each(function (v) { h[v] = true; });
> return a.filter(function (v) { return !h.hasOwnProperty(v); });
> },
>
> If the values are all numbers (and there are no missing properties):-

JFTR: Generally, that would work if the values were not all numbers, too.
However, one would have to take precautions that built-in properties are not
overwritten.

> var m = [], r = [];

Did you mean

var m = {}, r = [];

? For it does not make sense to use an Array instance where Array-ness is
irrelevant or misleading (numerically named properties P only become array
elements, increasing the Array instance's `length' property value, if they
meet the condition ToUint32(P) === P).

> for (var i = b.length; i-- {
> m[b] = true;
> }
> for (i = a.length; i-- { // Changes order
> if (!m[a]) {
> r.push(a);
> }
> }
> return r;
>
> If order matters, change the direction of the loops (or return
> r.reverse()).
>
> For sparsely populated arrays, for-in loops (with appropriate filters)
> would be faster.

Or, if you would sort both arrays using the same comparator, you could end
up with requiring no value mapping at all, depending on the interpretation
of the specifications.

PointedEars
--
Anyone who slaps a 'this page is best viewed with Browser X' label on
a Web page appears to be yearning for the bad old days, before the Web,
when you had very little chance of reading a document written on another
computer, another word processor, or another network. -- Tim Berners-Lee

Thomas 'PointedEars' Lahn, Dec 18, 2009
7. ### David MarkGuest

On Dec 18, 2:29 pm, Thomas 'PointedEars' Lahn <>
wrote:
> David Mark wrote:
> > Scott Sauyet wrote:
> >> > If I have two unsorted Javascript arrays, how do I compute the minus
> >> > operation?  In other words, I have arrays A and B and I want to know A
> >> > - B, the elements in A that do not belong to B.
> >> A good discussion on this is available here:
> >>http://tinyurl.com/ybxulzy

>
> > Depends on your definition of good.  And I'm not sure it is the same
> > question as the array contents are specified to be numbers only,

>
> It is the same question, however a bit vague, too.  One would need to define
> first whether, if A = [x, x] and B = [x], A - B would be [] or [x] asthere
> is an interpretation so that there was an `x in A' that `does not not to B'.
>
> > despite some of the odd solutions that followed:-

>
> > minusAB : function (a, b) {
> >     var h = {};
> >     b.each(function (v) { h[v] = true; });
> >     return a.filter(function (v) { return !h.hasOwnProperty(v); });
> >   },

>
> > If the values are all numbers (and there are no missing properties):-

>
> JFTR: Generally, that would work if the values were not all numbers, too.
> However, one would have to take precautions that built-in properties are not
> overwritten.

And if each and filter are supported, as well as hasOwnProperty.

>
> > var m = [], r = [];

>
> Did you mean
>
>   var m = {}, r = [];

No.

>
> ?  For it does not make sense to use an Array instance where Array-nessis
> irrelevant or misleading (numerically named properties P only become array
> elements, increasing the Array instance's `length' property value, if they
> meet the condition ToUint32(P) === P).

Yes, fair enough. The linked examples presented integers. Obviously,
the exact nature of the contents must be specified. And yes, using m
= {} would make it work in more cases.

>
> > for (var i = b.length; i-- {
> >    m[b] = true;
> > }
> > for (i = a.length; i-- { // Changes order
> >    if (!m[a]) {
> >       r.push(a);
> >    }
> > }
> > return r;

>
> > If order matters, change the direction of the loops (or return
> > r.reverse()).

>
> > For sparsely populated arrays, for-in loops (with appropriate filters)
> > would be faster.

>
> Or, if you would sort both arrays using the same comparator, you could end
> up with requiring no value mapping at all, depending on the interpretation
> of the specifications.

Yes.

David Mark, Dec 18, 2009
8. ### Asen BozhilovGuest

> I want to know A
> - B, the elements in A that do not belong to B.

What exactly mean that?

Elements in A for which:

ToString(A) != ToString(eachElementsInB) ?

What will be output in next cases:

var A = [{}, {}],
B = [];

var f = function(){},
A = [function(){}, f,],
B = [function(){}];

If you define what exactly want to do it, perhaps you can write
algorithm. But if is that your homework. Before you want whole code,

Regards.

Asen Bozhilov, Dec 18, 2009
9. ### Asen BozhilovGuest

Asen Bozhilov wrote:

Should be:

> var f = function(){},
>     A = [function(){}, f],
>     B = [function(){}];

Asen Bozhilov, Dec 18, 2009
10. ### Thomas 'PointedEars' LahnGuest

David Mark wrote:

> Thomas 'PointedEars' Lahn wrote:
>> David Mark wrote:
>> > despite some of the odd solutions that followed:-

>>
>> > minusAB : function (a, b) {
>> > var h = {};
>> > b.each(function (v) { h[v] = true; });
>> > return a.filter(function (v) { return !h.hasOwnProperty(v); });
>> > },

>>
>> > If the values are all numbers (and there are no missing properties):-

>>
>> JFTR: Generally, that would work if the values were not all numbers, too.
>> However, one would have to take precautions that built-in properties are
>> not overwritten.

>
> And if each and filter are supported, as well as hasOwnProperty.

That is not required. I was referring, perhaps unwisely in-between, to the
approach below.

>> [...] it does not make sense to use an Array instance where Array-ness
>> is irrelevant or misleading (numerically named properties P only become
>> array elements, increasing the Array instance's `length' property value,
>> if they meet the condition ToUint32(P) === P).

>
> Yes, fair enough. The linked examples presented integers. Obviously,
> the exact nature of the contents must be specified. And yes, using m
> = {} would make it work in more cases.

That I am not sure of, considering that many properties of Array instances
are inherited from Object.prototype via Array.prototype and would not be
overwritten (but shadowed) by an assignment. But it would probably save
more memory.

PointedEars
--
Danny Goodman's books are out of date and teach practices that are
positively harmful for cross-browser scripting.
-- Richard Cornford, cljs, <cife6q\$253\$1\$> (2004)

Thomas 'PointedEars' Lahn, Dec 18, 2009
11. ### Dr J R StocktonGuest

In comp.lang.javascript message <04a01259-1bc9-4e7d-9435-16f023dee81d@v7
<> posted:

>If I have two unsorted Javascript arrays, how do I compute the minus
>operation? In other words, I have arrays A and B and I want to know A
>- B, the elements in A that do not belong to B.

If you can sort the arrays, then you can consider them as stacks, and
compare the top items for > = <. That gives the necessary information
about at least one of the top items. Pop what can now be popped, and
repeat until empty.

If the elements have an adequate toString method, you can do something
based on

X = {}
for (J=0 ; J<B.length ; J++) X[B.toString()] = 1
for (J=0 ; J<A.length ; J++) if (!X[A.toString()]) Found one!

--
(c) John Stockton, Surrey, UK. ?@merlyn.demon.co.uk Turnpike v6.05 MIME.
Web <URL:http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms, & links.
Proper <= 4-line sig. separator as above, a line exactly "-- " (RFCs 5536/7)
Do not Mail News to me. Before a reply, quote with ">" or "> " (RFCs 5536/7)

Dr J R Stockton, Dec 20, 2009
12. ### Scott SauyetGuest

On Dec 18, 2:00 pm, David Mark <> wrote:
> On Dec 18, 12:59 pm, Scott Sauyet <> wrote:
>> On Dec 18, 9:51 am, laredotornado <> wrote:

>
>>> If I have two unsorted Javascript arrays, how do I compute the minus
>>> operation?  In other words, I have arrays A and B and I want to know A
>>> - B, the elements in A that do not belong to B.

>>
>> A good discussion on this is available here:
>>    http://tinyurl.com/ybxulzy

>
> Depends on your definition of good.

As always.

> And I'm not sure it is the same
> question as the array contents are specified to be numbers only,
> despite some of the odd solutions that followed:-

I didn't see either from the OP of this thread or the original
question on the linked document anything that implied the sets
contained only numbers. And one of the early examples in the linked
document in fact contained a mix of numbers and strings.

It was odd, though that the OP specified the logical notion of sets
(for which there is no notion of order/position) and the
implementation of arrays (for which order/position is inherent.)

> minusAB : function (a, b) {
>     var h = {};
>     b.each(function (v) { h[v] = true; });
>     return a.filter(function (v) { return !h.hasOwnProperty(v); });
>   },

My own solution kept with the arrays:

function setDiff(A, B) {
var C = [];
A.forEach(function(el) {if (B.indexOf(el) < 0) C.push(el);});
return C;
}

I originally pointed to the document out of concern that Thomas Lahn
had it right that this was a homework problem. There is some
pedagogical benefit to the discussions on that page that wouldn't be
found just by supplying an answer here. However, knowing that I've
had to solve that problem in the real world several times, and
knowing
that the OP has been posting programming questions in various forums
for years, in retrospect, it seems likely that it wasn't a homework
problem.

-- Scott

Scott Sauyet, Dec 21, 2009
13. ### David MarkGuest

On Dec 21, 10:15 am, Scott Sauyet <> wrote:
> On Dec 18, 2:00 pm, David Mark <> wrote:
>
> > On Dec 18, 12:59 pm, Scott Sauyet <> wrote:
> >> On Dec 18, 9:51 am, laredotornado <> wrote:

>
> >>> If I have two unsorted Javascript arrays, how do I compute the minus
> >>> operation?  In other words, I have arrays A and B and I want to know A
> >>> - B, the elements in A that do not belong to B.

>
> >> A good discussion on this is available here:
> >>    http://tinyurl.com/ybxulzy

>
> > Depends on your definition of good.

>
> As always.
>
>
> >                                     And I'm not sure it is the same
> > question as the array contents are specified to be numbers only,
> > despite some of the odd solutions that followed:-

>
> I didn't see either from the OP of this thread or the original
> question on the linked document anything that implied the sets
> contained only numbers.

There was no indication from the OP. The linked document had an
example near the top that was all numbers.

> And one of the early examples in the linked
> document in fact contained a mix of numbers and strings.

There are some of those too.

>
> It was odd, though that the OP specified the logical notion of sets
> (for which there is no notion of order/position) and the
> implementation of arrays (for which order/position is inherent.)

Only the OP knows what he is after.

>
> > minusAB : function (a, b) {
> >     var h = {};
> >     b.each(function (v) { h[v] = true; });
> >     return a.filter(function (v) { return !h.hasOwnProperty(v); });
> >   },

>
> My own solution kept with the arrays:
>
>     function setDiff(A, B) {
>         var C = [];
>         A.forEach(function(el) {if (B.indexOf(el) < 0) C.push(el);});
>         return C;
>     }

As the poster in the linked example specified that FF-only was
acceptable, this is fine. I certainly like it better than some of the
other examples posted.

David Mark, Dec 21, 2009
14. ### Thomas 'PointedEars' LahnGuest

Dr J R Stockton wrote:

> If the elements have an adequate toString method, you can do something
> based on
>
> X = {}
> for (J=0 ; J<B.length ; J++) X[B.toString()] = 1
> for (J=0 ; J<A.length ; J++) if (!X[A.toString()]) Found one!

That is nonsense, not to mention very inefficient. Probably you meant
something along these lines:

var x = {};
for (var j = 0, len = B.length; j < len; j++) x[B[j]] = true;
for (j = 0, len = A.length; j < len; j++) if (!x[A[j]]) found_one();

(If a value that is used in a bracket property accessor's parameter can be
converted to an object that has a toString() method, this method is called
and its return value is used implicitly. See ES3F/ES5, 11.2.1.)

However, we have already established that this would be potentially harmful
as built-in and inherited properties could interfere both with reading and
writing the value. So precautions need to be taken that this is less likely
to happen.

PointedEars
--
var bugRiddenCrashPronePieceOfJunk = (
navigator.userAgent.indexOf('MSIE 5') != -1
&& navigator.userAgent.indexOf('Mac') != -1
) // Plone, register_function.js:16

Thomas 'PointedEars' Lahn, Dec 22, 2009
15. ### Scott SauyetGuest

On Dec 21, 9:47 pm, Thomas 'PointedEars' Lahn <>
wrote:
> [ ... ]
>   var x = {};
>   for (var j = 0, len = B.length; j < len; j++) x[B[j]] = true;
>   for (j = 0, len = A.length; j < len; j++) if (!x[A[j]]) found_one();
>
> [ ... ]
> However, we have already established that this would be potentially harmful
> as built-in and inherited properties could interfere both with reading and
> writing the value.  So precautions need to be taken that this is less likely
> to happen.

And it is also less general than a solution based upon object
equality. There might be some efficiencies gained by such a
mechanism, depending upon how efficient property look-up is compared
to an array iteration and comparison. But if you don't know for
certain that different objects have different toString() outputs,
this
might falsely exclude some objects from the set difference.

A number of the suggestions in the document I referenced share this
limitation as well.

-- Scott

Scott Sauyet, Dec 22, 2009
16. ### Dr J R StocktonGuest

In comp.lang.javascript message <924e8902-7f58-4fac-9b85-d406f8cb62b7@u2
0g2000vbq.googlegroups.com>, Tue, 22 Dec 2009 07:45:12, Scott Sauyet
<> posted:
>
>And it is also less general than a solution based upon object
>equality. There might be some efficiencies gained by such a
>mechanism, depending upon how efficient property look-up is compared
>to an array iteration and comparison.

General property lookup ought to be by an algorithm of a more efficient
order than iterative search, it ought also to be done by ASM/C-type
programming rather than by script. For objects with many properties, it
should therefore be of a faster order than iteratively searching an
array.

TL evidently does not understand what "based on" means.

--
(c) John Stockton, nr London UK. ?@merlyn.demon.co.uk DOS 3.3 6.20 ; WinXP.
Web <URL:http://www.merlyn.demon.co.uk/> - FAQqish topics, acronyms & links.
PAS EXE TXT ZIP via <URL:http://www.merlyn.demon.co.uk/programs/00index.htm>
My DOS <URL:http://www.merlyn.demon.co.uk/batfiles.htm> - also batprogs.htm.

Dr J R Stockton, Dec 23, 2009
17. ### Thomas 'PointedEars' LahnGuest

Dr J R Stockton wrote:

> Scott Sauyet posted:
>> And it is also less general than a solution based upon object
>> equality. There might be some efficiencies gained by such a
>> mechanism, depending upon how efficient property look-up is compared
>> to an array iteration and comparison.

>
> General property lookup ought to be by an algorithm of a more efficient
> order than iterative search, it ought also to be done by ASM/C-type
> programming rather than by script. For objects with many properties, it
> should therefore be of a faster order than iteratively searching an
> array.
>
> TL evidently does not understand what "based on" means.

Evidently you do not know that there are no good solutions based on wrong
approaches.

PointedEars
--
Use any version of Microsoft Frontpage to create your site.
(This won't prevent people from viewing your source, but no one
will want to steal it.)
-- from <http://www.vortex-webdesign.com/help/hidesource.htm> (404-comp.)

Thomas 'PointedEars' Lahn, Dec 25, 2009