How to compute the difference between two arrays?

L

laredotornado

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
 
E

Evertjan.

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.
 
T

Thomas 'PointedEars' Lahn

laredotornado said:
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
 
D

David Mark

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.
 
T

Thomas 'PointedEars' Lahn

David said:
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
 
D

David Mark

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.
 
A

Asen Bozhilov

laredotornado said:
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,
please show what you wrote.

Regards.
 
T

Thomas 'PointedEars' Lahn

David said:
Thomas said:
David said:
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
 
D

Dr J R Stockton

In comp.lang.javascript message <04a01259-1bc9-4e7d-9435-16f023dee81d@v7
g2000pro.googlegroups.com>, Fri, 18 Dec 2009 06:51:11, laredotornado
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!
 
S

Scott Sauyet

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
 
D

David Mark

As always.  :)
  


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.
 
T

Thomas 'PointedEars' Lahn

Dr said:
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
 
S

Scott Sauyet

[ ... ]
  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
 
D

Dr J R Stockton

In comp.lang.javascript message <924e8902-7f58-4fac-9b85-d406f8cb62b7@u2
0g2000vbq.googlegroups.com>, Tue, 22 Dec 2009 07:45:12, Scott Sauyet
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.
 
T

Thomas 'PointedEars' Lahn

Dr said:
Scott Sauyet posted:

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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,901
Latest member
Noble71S45

Latest Threads

Top