How to compute the difference between two arrays?

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

  1. 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
     
    laredotornado, Dec 18, 2009
    #1
    1. Advertising

  2. laredotornado

    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.
    (Please change the x'es to dots in my emailaddress)
     
    Evertjan., Dec 18, 2009
    #2
    1. Advertising

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


    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
    #3
  4. laredotornado

    Scott Sauyet Guest

    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
    #4
  5. laredotornado

    David Mark Guest

    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
    #5
  6. David Mark wrote:

    > Scott Sauyet wrote:
    >> 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,


    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
    #6
  7. laredotornado

    David Mark Guest

    On Dec 18, 2:29 pm, Thomas 'PointedEars' Lahn <>
    wrote:
    > David Mark wrote:
    > > Scott Sauyet wrote:
    > >> 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,

    >
    > 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
    #7
  8. laredotornado wrote:

    > 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.
     
    Asen Bozhilov, Dec 18, 2009
    #8
  9. Asen Bozhilov wrote:

    Should be:

    > var f = function(){},
    >     A = [function(){}, f],
    >     B = [function(){}];
     
    Asen Bozhilov, Dec 18, 2009
    #9
  10. 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
    #10
  11. In comp.lang.javascript message <04a01259-1bc9-4e7d-9435-16f023dee81d@v7
    g2000pro.googlegroups.com>, Fri, 18 Dec 2009 06:51:11, laredotornado
    <> 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
    #11
  12. laredotornado

    Scott Sauyet Guest

    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
    #12
  13. laredotornado

    David Mark Guest

    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
    #13
  14. 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
    #14
  15. laredotornado

    Scott Sauyet Guest

    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
    #15
  16. 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
    #16
  17. 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
    #17
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. W. eWatson
    Replies:
    4
    Views:
    322
    Ari Makela
    Sep 1, 2008
  2. Kev Jackson
    Replies:
    2
    Views:
    131
  3. The Poor
    Replies:
    9
    Views:
    153
    David K. Wall
    Sep 29, 2003
  4. shashi
    Replies:
    17
    Views:
    436
    Guest
    Apr 13, 2006
  5. PerlFAQ Server
    Replies:
    0
    Views:
    275
    PerlFAQ Server
    Feb 2, 2011
Loading...

Share This Page