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

Groups > comp.lang.javascript > #24531

Re: Difference between two arrays

Show all headers | View raw

In comp.lang.javascript message <8fb98ef4-ceba-4573-a64c-c45cf9ebdf69@go
oglegroups.com>, Sat, 31 May 2014 14:59:05, "Michael Haufe (TNO)"
<tno@thenewobjective.com> posted:

>On Wednesday, May 28, 2014 12:22:39 PM UTC-5, Dr J R Stockton wrote:
>[...]
>>
>> Create a third array which contains the first array once and the second
>> array twice.  Then use sort() to get a fourth array from the third.
>> Then do a linear scan of the fourth array looking for consecutive equal
>> elements.  Singlets occur in only the first array, doublets only in the
>> second, and triplets occur in both.  You can then store copies of the
>> elements according to multiplicity in three more arrays.
>> Of course, you do not copy elements; you only make new pointers to them.
>> The method should be reasonably efficient, and extends to comparing more
>> than two arrays.
>
>- JavaScript sort is an in-place sort, so I don't know where this 4th
>array is coming from.

The fourth array is "in" the same variable as the third, but it is not
the same as it was before the sort.  Nomenclature, not multiplicity.

>- Would you mind qualifying "reasonably efficient"? I'm not convinced
>of this using what I think is your approach, especially as more than
>two arrays are used.

In non-trivial cases, the time taken will be dominated by the sort,
which for N-element arrays should take no more than O(N*log(N)) time.
The other operations all take O(N) time.

Some other approaches seem likely to compare every element of one array
with every element of the other, which is O(N^2) time.

I immediately thought of that method because I often use it in DOS
Batch, where it is easy to write given some auxiliary programs that I
already have in Pascal.  I expect it would be faster, though, if I did
it all in Pascal.


OTOH, it will be better, perhaps, to use a variety of merge sort :-

First sort each of the original arrays, or copies of them, into
ascending order downwards.  Then pop the smallest top element or
elements until there are no more top elements of equal value.  Then
contemplate how many have been popped from each array, which gives what
the OP wants to know about elements of that value.  Repeat popping until
all the sorted arrays are empty.  Popping and contemplation is simpler
if the original arrays are known not to contain duplicates.

The time for that should still, for large N, be dominated by the
sorting; but the sorts are smaller.

-- 
 (c) John Stockton, nr London, UK.   E-mail, see Home Page.    Turnpike v6.05.
 Website  <http://www.merlyn.demon.co.uk/> - w. FAQish topics, links, acronyms
 PAS EXE etc. : <http://www.merlyn.demon.co.uk/programs/> - see in 00index.htm
 Dates - miscdate.htm estrdate.htm js-dates.htm pas-time.htm critdate.htm etc.

Back to comp.lang.javascript | Previous | Next — Previous 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