Velocity Reviews > How to compute the difference between two arrays?

# How to compute the difference between two arrays?

Guest
Posts: n/a

 12-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

Evertjan.
Guest
Posts: n/a

 12-18-2009
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.

Thomas 'PointedEars' Lahn
Guest
Posts: n/a

 12-18-2009

> 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

Scott Sauyet
Guest
Posts: n/a

 12-18-2009
On Dec 18, 9:51*am, laredotornado <(E-Mail Removed)> 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

David Mark
Guest
Posts: n/a

 12-18-2009
On Dec 18, 12:59*pm, Scott Sauyet <(E-Mail Removed)> wrote:
> On Dec 18, 9:51*am, laredotornado <(E-Mail Removed)> 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[i]] = true;
}
for (i = a.length; i-- { // Changes order
if (!m[a[i]]) {
r.push(a[i]);
}
}
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.

Thomas 'PointedEars' Lahn
Guest
Posts: n/a

 12-18-2009
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[i]] = true;
> }
> for (i = a.length; i-- { // Changes order
> if (!m[a[i]]) {
> r.push(a[i]);
> }
> }
> 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

David Mark
Guest
Posts: n/a

 12-18-2009
On Dec 18, 2:29*pm, Thomas 'PointedEars' Lahn <(E-Mail Removed)>
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[i]] = true;
> > }
> > for (i = a.length; i-- { // Changes order
> > * *if (!m[a[i]]) {
> > * * * r.push(a[i]);
> > * *}
> > }
> > 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.

Asen Bozhilov
Guest
Posts: n/a

 12-18-2009

> 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[i]) != 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
Guest
Posts: n/a

 12-18-2009
Asen Bozhilov wrote:

Should be:

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

Thomas 'PointedEars' Lahn
Guest
Posts: n/a

 12-18-2009
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\$(E-Mail Removed)> (2004)