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

Groups > comp.lang.javascript > #24434 > unrolled thread

Difference between two arrays

Back to article view | Back to comp.lang.javascript

Contents

  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

Page 1 of 2  [1] 2  Next page →

#24434 — Difference between two arrays

If I have two "simple" arrays and I need to create a third array of 
elements that are only in one of the arrays. I found this

Array.prototype.difference = function (a) {
   return this.filter(function (i) {
     return !(a.indexOf(i) > -1);
   });
};

which I don't fully understand but the issue with it that I have is that 
I need to run it on both arrays to get all the differences. For example

var arrX = [1, 2, 4, 6, 8],
     arrY = [4, 8, 9];

var arrRes1 = arrX.difference(arrY)); // 1,2,6
var arrRes2 = arrY.difference(arrX)); // 9

var arrRes = arrRes1.concat(arrRes2); // 1,2,6,9

Andrew Poulos

[toc] | [next] | [standalone]

#24436

On Tue, 27 May 2014 11:55:03 +1000, Andrew Poulos wrote:

> If I have two "simple" arrays and I need to create a third array of
> elements that are only in one of the arrays. I found this
> 
> Array.prototype.difference = function (a) {
>    return this.filter(function (i) {
>      return !(a.indexOf(i) > -1);
>    });
> };
> 
> which I don't fully understand but the issue with it that I have is that
> I need to run it on both arrays to get all the differences. For example

It's not finding the differences between two arrays, it's finding the 
elements of one array which are not in the other array.

Think of it like an array subtraction:

arr1 = [ a, b, c, d, e ]
arr2 = [ b, c, d, e, f ]

arr1 - arr2 = those elements of arr1 that are not in arr2 = [ a ]
arr2 - arr1 = those elements of arr2 that are not in arr1 = [ f ]

( arr1 - arr2 ) + ( arr2 - arr1 ) 

In terms of set theory, you're taking the union of the set differences to 
create the symmetric difference.

-- 
Denis McMahon, denismfmcmahon@gmail.com

[toc] | [prev] | [next] | [standalone]

#24437

On Monday, May 26, 2014 9:55:03 PM UTC-4, Andrew Poulos wrote:
> If I have two "simple" arrays and I need to create a third array of 
> 
> elements that are only in one of the arrays. I found this
> 
> 
> 
> Array.prototype.difference = function (a) {
> 
>    return this.filter(function (i) {
> 
>      return !(a.indexOf(i) > -1);
> 
>    });
> 
> };
> 
> 
> 
> which I don't fully understand but the issue with it that I have is that 
> 
> I need to run it on both arrays to get all the differences. For example
> 
> 
> 
> var arrX = [1, 2, 4, 6, 8],
> 
>      arrY = [4, 8, 9];
> 
> 
> 
> var arrRes1 = arrX.difference(arrY)); // 1,2,6
> 
> var arrRes2 = arrY.difference(arrX)); // 9
> 
> 
> 
> var arrRes = arrRes1.concat(arrRes2); // 1,2,6,9
> 
> 
> 
> Andrew Poulos

If your code is doing this often and the arrays have more than just a few 
elements then you might run into performance issues. I think that .indexOf
just implements a linear search hence the code you show is O(mn) where m, n are 
the lengths of the arrays (so roughly 1,000,000 comparisons if m = n = 1000). 
It might be better to first sort the arrays and then replace .indexOf with a
binary search function (giving you something like O((m+n)(log(m) + log(n))). 
For things like m = n = 1000 this would be an order of magnitude quicker. On 
the other hand, for small m and n the time spent sorting might be hard to 
justify.

If you are using these arrays as sets and they have the property that each
element occurs exactly once in each array, a slick approach would be to 
concatenate the two arrays then sort the result something like 

var arrZ = arrX.concat(arrY);
arrZ.sort()

then -- elements in the symmetric difference of arrX and arrY will be 
elements of arrZ with the property that they occur only once. Something like

//untested!
var arrW = new Array();
var i = 0;
while (i < arrZ.length - 1)
{
    if(arrZ[i] === arrZ[i+1])
    {
       i += 2; //skip over the duplicate
    }
    else
    {
      arrW.push(arrZ[i]);
      i++;
    }
}

This won't work if arrX and/or arrY already contain duplicates though in 
that case you could sort and remove duplicated before using the above code.

[toc] | [prev] | [next] | [standalone]

#24504

On 2014-05-27, John C <rescattered@gmail.com> wrote:
>
> If your code is doing this often and the arrays have more than just a few 
> elements then you might run into performance issues. I think that .indexOf
> just implements a linear search hence the code you show is O(mn) where m, n are 
> the lengths of the arrays (so roughly 1,000,000 comparisons if m = n = 1000). 
> It might be better to first sort the arrays and then replace .indexOf with a
> binary search function (giving you something like O((m+n)(log(m) + log(n))). 
> For things like m = n = 1000 this would be an order of magnitude quicker. On 
> the other hand, for small m and n the time spent sorting might be hard to 
> justify.

A sort (say alphanumeric) and then a binary search might be quicker.

In perl I have often seen scripts which simply set an unordered list
to be searched as the keys of a hash (associative array) and then check
if the key exists since, in creating a hash, perl is rather efficient
in creating a structure (heap?) enabling efficient searching.

There are so many interpreters/JIT engines for Javascript that I don't
know if creating an associative array with keys being the elements of
an array (then checking for assoc_array[key])) would drastically
improve the search process.

[toc] | [prev] | [next] | [standalone]

#24506

Spamless wrote:
^^^^^^^^
Who?
 
> A sort (say alphanumeric) and then a binary search might be quicker.
> 
> In perl I have often seen scripts which simply set an unordered list
> to be searched as the keys of a hash (associative array) and then check
> if the key exists since, in creating a hash, perl is rather efficient
> in creating a structure (heap?) enabling efficient searching.
> 
> There are so many interpreters/JIT engines for Javascript

There is no Javascript.

<http://PointedEars.de/es-matrix>

> that I don't know if creating an associative array with keys being the
> elements of an array (then checking for assoc_array[key])) would
> drastically improve the search process.

There are no built-in associative arrays in ECMAScript (ES).  “…[…]” is the 
bracket “property accessor” syntax for *all* objects (ES); it is _not_ an 
“array operator” (Flanagan).

-- 
PointedEars
FAQ: <http://PointedEars.de/faq> | SVN: <http://PointedEars.de/wsvn/>
Twitter: @PointedEars2 | ES Matrix: <http://PointedEars.de/es-matrix>
Please do not Cc: me. / Bitte keine Kopien per E-Mail.

[toc] | [prev] | [next] | [standalone]

#24518

On 2014-05-31, Thomas 'PointedEars' Lahn <PointedEars@web.de> wrote:
>  
> There are no built-in associative arrays in ECMAScript (ES).  ??????[???]??? is the 
> bracket ???property accessor??? syntax for *all* objects (ES); it is _not_ an 
> ???array operator??? (Flanagan).

Again, you are in the wrong group.

The ECMAScript group is elsewhere.

(Are you the one that thinks that Javascript supports UTF-16?,
 16 bit Unicode? Only four functions do and it is not
 16 bit codepoints. It is a 16 bit encoding of unicode.
 And believes that "escape" does not exist and that "%xx"
 format as "escaped" data is a figment of all our, or at
 my, imaginations?)

Your response is irrelevant.

Does creating an assoicative array with keys from an unordered
list enable efficient searching of the list by looking for the
key? As keys are meant quickly to be found they are likely
stored in an efficiently searchable structure.

If that is true, it can be used to remove the need for
presorting followed by a bisection search.

Some people use it. I take it you believe it doesn't work
(much as you believe that decodeURIComponent(escape(string))
cannot possibly be used to convert UTF8 encoded text to 
Javascript strings - in UTF16 which Javascript may not
properly recognize).

[toc] | [prev] | [next] | [standalone]

#24521

Spamless wrote:
^^^^^^^^
This is Usenet.  Please fix.

> On 2014-05-31, Thomas 'PointedEars' Lahn <PointedEars@web.de> wrote:
>> There are no built-in associative arrays in ECMAScript (ES). 
>> ??????[???]??? is the bracket ???property accessor??? syntax for *all*
>> objects (ES); it is _not_ an ???array operator??? (Flanagan).

Your newsreader is borken.  There were Unicode characters in my posting 
where there are question marks in your quotation, and they were properly 
declared.  (So much for your understanding Unicode.)

> Again, you are in the wrong group.

Nonsense.
 
> The ECMAScript group is elsewhere.

This is the international JavaScript newsgroup.

This is also the international ECMAScript newsgroup.  It has become that in 
1997 CE, when Netcape JavaScript 1.1 became one of two implementations of 
ECMAScript (the other was Microsoft JScript 1.0).  Since then, there have 
been other ECMAScript implementations, most notably Opera ECMAScript 
(discontinued), Mozilla JavaScript (successor to Netscape JavaSCript in 
Mozilla-based software), KDE JavaScript, Apple/WebKit JavaScriptCore, and 
Google V8 JavaScript.

This is also the international DOM (Document Object Model) newsgroup as far 
as ECMAScript is concerned, because the DOM API is primarily used with 
ECMAScript implementations as the DOM is primarily used in Web browsers 
which is the runtime environment that primarily employs them.  (So much that 
the “type” attribute of the HTML5 “script” element is optional and an 
ECMAScript implementation is now officially the default scripting language.)  
And AFAIK there is no DOM-specific newsgroup that would cover *all* DOM 
implementations that can be used with ECMAScript implementations (primarily, 
in Web browsers).

I think it is also the international JScript newsgroup now because 
<news:microsoft.public.scripting.jscript> not only looks quite dead (which 
might be due to the fact that Microsoft shut down many of their newsgroups a 
few years ago), but also may not be carried by all news servers.
 
> (Are you the one that thinks that Javascript supports UTF-16?,
>  16 bit Unicode?

I am certainly not someone who believes that, because I know for a fact that 
there is no Javascript.

>  Only four functions do and it is not 16 bit codepoints. It is a 16 bit
>  encoding of unicode.

UTF-16 *is* the 16-bit encoding of Unicode, whereas “16-bit” means 16-bit 
code *units*, _not_ code points:

<http://www.unicode.org/faq/utf_bom.html>

ECMAScript specifies that conforming implementations must support Unicode 
characters up to code point U+FFFF (the Basic Multilingual Plane).  The 
hexadecimal value FFFF takes two 8-bit bytes or 16 bits, and can be encoded 
in UTF-16 with one code unit.

,-<http://ecma-international.org/ecma-262/5.1/#sec-8.4>
| 
| 8.4 The String Type
| 
| The String type is the set of all finite ordered sequences of zero or more 
| 16-bit unsigned integer values (“element”). The String type is generally 
| used to represent textual data in a running ECMAScript program, in which
| case each element in the String is treated as a code unit value (see 
| Clause 6). Each element is regarded as occupying a position within the
| sequence. These positions are indexed with nonnegative integers.
| The first element (if any) is at position 0, the next element (if any) at
| position 1, and so on. The length of a String is the number of of elements 
| elements (i.e., 16-bit values) within it. The empty String has length zero
| and therefore contains no elements.
| 
| When a String contains actual textual data, each element is considered to
| be a single UTF-16 code unit.  Whether or not this is the actual storage
| format of a String, the characters within a String are numbered by their
| initial code unit element position as though they were represented using
| UTF-16. All operations on Strings (except as otherwise stated) treat them
| as sequences of undifferentiated 16-bit unsigned integers; they do not
| ensure the resulting String is in normalised form, nor do they ensure
| language-sensitive results.
| 
| NOTE
| The rationale behind this design was to keep the implementation of Strings
| as simple and high-performing as possible. The intent is that textual data
| coming into the execution environment from outside (e.g., user input, text
| read from a file or received over the network, etc.) be converted to
| Unicode Normalised Form C before the running program sees it. Usually this
| would occur at the same time incoming text is converted from its original
| character encoding to Unicode (and would impose no additional overhead).
| Since it is recommended that ECMAScript source code be in Normalised Form
| C, string literals are guaranteed to be normalised (if source text is
| guaranteed to be normalised), as long as they do not contain any Unicode
| escape sequences.

As for supporting code points beyond the BMP in ECMAScript implementations, 
see JSX:string/unicode.js.  (This is possible because ECMAScript speaks of 
16-bit “elements”, _not_ code points.  Characters beyond the BMP can be 
encoded with two UTF-16 code units.)

>  And believes that "escape" does not exist

escape() does exist as a proprietary, originally not Unicode-safe feature of 
several ECMAScript implementations for backwards compatibility.  A variant 
of escape() is specified in Annex B (informational, as annexes go) of the 
ECMAScript Language Specification (of the 5.1 Edition at least); this means 
that a conforming implementation does not need to implement it.  (However, 
Google V8 JavaScript in Chromium 34 does.  I should add a test case to the 
Matrix.)

The string values this variant generates for Unicode characters beyond the 
Basic Latin and Latin-1 Supplement Unicode ranges ("%uXXXX") do _not_ comply 
with RFC 3986; therefore, escape() cannot safely be used to encode URIs or 
URI components.  And given that escape() is proprietary, it cannot safely be 
used to encode Unicode characters at all (because the unescape() of another 
implementation may not support the format that is employed by escape() of 
the first implementation for characters beyond those ranges, if there are 
such methods).

The recommendation is to use the standard functions (methods of the global 
object) encodeURI() and encodeURIComponent() instead because they encode 
*all* Unicode characters to percent-encoded UTF-8 code units as specified by 
RFC 3986 that are considered “unsafe” by that standards-track RFC, and as my 
work shows they are “safe” features by now.  decodeURI() and 
decodeURIComponent() are their standard counterparts.

<http://PointedEars.de/es-matrix/?filter=URI>

>  and that "%xx" format as "escaped" data is a figment of all our, or at
>  my, imaginations?)

No, you must have completely misunderstood what I wrote back then.
 
> Your response is irrelevant.

Hardly.  As you could have found out if you had followed the reference and 
read the “Foreword and Rationale” section of the ECMAScript Support Matrix, 
when I write “ECMAScript” I mean both the standard and its implementations.

I am telling you that you cannot take an term invented out of thin air that 
does not have a proper definition *anywhere*, like “Javascript”, and apply 
it to all ECMAScript implementations without considering the differences 
between those implementations.

Although similar, those are *different* programming languages.  They are the 
result of the implementation of a language specification, a standard.  So 
*that* term *is* well-defined.  It is a special kind of standard though, 
because it allows its conforming implementation to extend it considerably 
(§2); this provision once allowed the two existing implementations to be 
considered conforming (finding common ground between Netscape and Microsoft 
was the goal of the first Edition), and now allows implementations of it to 
add features that may later be standardized (as we have seen and are seeing 
with ECMAScript Editions 5 and beyond.)

So there can be no “Javascript interpreter” because there is no 
“Javascript”.  That there was is a figment of *your* imagination because you 
are not capable or willing to understand the connections yet, 
*over*simplifiying matters so that you are able to understand what you 
otherwise could not comprehend.  You can continue to do so, but you will not 
arrive at the truth this way.  Instead, this way lies madness.
 
> Does creating an assoicative array with keys from an unordered
> list enable efficient searching of the list by looking for the
> key?

If there was such a thing as an associative array in a programming language, 
yes.  However, there is a difference between an associative array and an 
object that can work like such a data structure: by contrast to the 
associative array, the object has and inherits properties of its own that 
are *not* elements of what one might superficially consider an "associative 
array".  And as the ECMAScript syntax uses the bracket property accessor 
syntax both for accessing array elements and accessing properties (because 
array elements are just properties with decimal names in a certain range), 
one has to be aware of the fact.

IOW, in order to have only a key-value relationship in an ECMAScript 
implementation like JavaScript, you do not need an array (and chances are 
you do not want to, because Array instances have and inherit more properties 
that would interfere); you just need an object.  In the simplest case, an 
Object instance, created in conforming implementations of ECMAScript 5.1 
Edition thus:

  var obj = Object.create(null);

Or equivalents of that (see jsx.object.getDataObject() in JSX:object.js); 
the important thing here is that the prototype chain of the object is empty 
so that in the best case it neither has nor inherits properties whose names 
could interfere with "array" items.  Otherwise you need to implement the 
concept of associative array in a more elaborate way, avoiding built-in 
properties through aliasing (see JSX:map.js for an example).

> As keys are meant quickly to be found they are likely
> stored in an efficiently searchable structure.

True.
 
> If that is true, it can be used to remove the need for
> presorting followed by a bisection search.

Also true, but you employing a straw man argument and you are missing the 
point.
 
> Some people use it.

It is an unfortunate truth that most people do not know what they are doing.

> I take it you believe it doesn't work

I *know* from more than a decade of experience with it that it does not work 
without considering all the facts.  Using the code

  var a = new Array();

  a["foo"] = "bar";

  /* 0 */
  a["length"]

  a["0"] = "bar";

  /* 1 */
  a["length"]

  a["length"] = 0;

  /* undefined */
  a["0"]

  /* "bar" */
  a["foo"]

  a[String(Math.pow(2, 32) - 1)] = "foo";

  /* 0 */
  a["length"]

  /* "foo" */
  a[String(Math.pow(2, 32) - 1)]

  a[String(Math.pow(2, 32) - 2)] = "bar";

  /* 4294967295 */
  a["length"]

  /* "bar" */ 
  a[String(Math.pow(2, 32) - 2)] 

one can observe two things: one, that

  a["foo"] = "bar";

does _not_ add an element to an "associative array" data structure; two, 
that "somehow magically" there is already an "element" with "key" “length” 
in that supposed to be empty "associative array", and that its value 
*seemingly* changes in erratic ways as "elements" are added (and removed).  
So an uninitiated observer who is quick to jump to conclusions would 
conclude from those observations that “Javascript” has associative arrays 
but that “Javascript” is a bit borken.  (The record shows.)

Of course, nothing is borken here and nothing is flawed but the 
understanding and logic of that observer.  Both observations are *actually* 
due to the fact that it is _not_ an associative array at all; it is an 
*object* with *properties* of which some are special.  (See ES 5.1, §15.4 
for details.)

> (much as you believe that decodeURIComponent(escape(string))
> cannot possibly be used to convert UTF8 encoded text to
> Javascript strings - in UTF16 which Javascript may not
> properly recognize).

Certainly it is possible to use decodeURI() and decodeURIComponent() to 
decode UTF-8 code units that are *percent-encoded according to RFC 3986*; 
that is their very purpose.

However, it is not the purpose of escape() to encode Unicode text like that, 
not least because it predates Unicode support in ECMAScript implementations.  
So if “decodeURIComponent(escape(string))” works, it is mere coincidence; in 
general, it should only work if the characters in “string” all have code 
points below U+0080 (i. e., are in the ASCII range).

-- 
PointedEars
FAQ: <http://PointedEars.de/faq> | SVN: <http://PointedEars.de/wsvn/>
Twitter: @PointedEars2 | ES Matrix: <http://PointedEars.de/es-matrix>
Please do not Cc: me. / Bitte keine Kopien per E-Mail.

[toc] | [prev] | [next] | [standalone]

#24526

Thomas 'PointedEars' Lahn wrote:

> IOW, in order to have only a key-value relationship in an ECMAScript
> implementation like JavaScript, you do not need an array (and chances are
> you do not want to, because Array instances have and inherit more
> properties that would interfere); you just need an object.  In the
> simplest case, an Object instance, created in conforming implementations
> of ECMAScript 5.1 Edition thus:
> 
>   var obj = Object.create(null);
> 
> Or equivalents of that (see jsx.object.getDataObject() in JSX:object.js);
> the important thing here is that the prototype chain of the object is
> empty so that in the best case it neither has nor inherits properties
> whose names could interfere with "array" items.  Otherwise you need to
> implement the concept of associative array in a more elaborate way,
  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> avoiding built-in properties through aliasing (see JSX:map.js for an
> example).

And, I forgot to emphasize, in general you need such a user-defined 
associative-array implementation to deal with "keys" that are not Strings.  
Because property names are primitive string values internally, and "keys" 
are converted to the String type.  For example, without user-defined 
getters/setters, a[1] and a["1"] are equivalent expressions.
 
-- 
PointedEars
FAQ: <http://PointedEars.de/faq> | SVN: <http://PointedEars.de/wsvn/>
Twitter: @PointedEars2 | ES Matrix: <http://PointedEars.de/es-matrix>
Please do not Cc: me. / Bitte keine Kopien per E-Mail.

[toc] | [prev] | [next] | [standalone]

#24439

Andrew Poulos <ap_prog@hotmail.com> writes:

> If I have two "simple" arrays and I need to create a third array of
> elements that are only in one of the arrays. I found this
>
> Array.prototype.difference = function (a) {
>   return this.filter(function (i) {
>     return !(a.indexOf(i) > -1);
>   });
> };
>
> which I don't fully understand

Me too.  I'd have thought that

  return this.filter(function (e) { return a.indexOf(e) === -1; });

would be easier to understand.  I don't like using i for an array
method callback unless it denotes and index, but that's just a small
style issue.  There may be a reason why !(a.indexOf(i) > -1) is better,
but I can't think of one, even after some study of language standard.

Anyway, the call constructs an array the includes only those elements of
"this" that can't be found in "a".

Depending on lots of unknowns, it may be faster to invert the arrays.
I.e. to show the presence of element x by setting a[x] to some specific
value, rather than have some index i at which a[i] === x.

This makes testing for membership fast, but at the expense of other
things.  In particular, unless the implementation is clever, a very wide
range of values can result is very large inverted arrays.

The symmetric difference then looks like this:

Array.prototype.symDiff = function (a) {
    var count = [];
    this.forEach(function (e) { count[e] = 1; });
    a.forEach(function (e) { count[e] = (count[e] || 0) | 2; });
    var result = [];
    count.forEach(function (e, i) { if (e !== 3) result.push(i); });
    return result;
};

This version deals with arrays that contain duplicates by using 1 to
mean "in array 1", 2 to mean "in array 2" and 3 (1|2) to mean "in
both".

In fact, if you are really working with sets, you might want to use this
inverted representation right form the start.  That will make many
set-like operations simpler and faster, but at the very least, test with
some real data first.

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#24441

Ben Bacarisse wrote:

> Andrew Poulos <ap_prog@hotmail.com> writes:
>> If I have two "simple" arrays and I need to create a third array of
>> elements that are only in one of the arrays. I found this
>>
>> Array.prototype.difference = function (a) {
>>   return this.filter(function (i) {
>>     return !(a.indexOf(i) > -1);
>>   });
>> };
>
> […]
> Anyway, the call constructs an array the includes only those elements of
> "this" that can't be found in "a".
> 
> Depending on lots of unknowns, it may be faster to invert the arrays.
> I.e. to show the presence of element x by setting a[x] to some specific
> value, rather than have some index i at which a[i] === x.

You can not simply invert arrays in ECMAScript implementations.  Arrays are 
objects, therefore keys are properties of an object.  Values whose string 
representation is the same as a property of the object can overwrite built-
in properties.
 
> This makes testing for membership fast, but at the expense of other
> things.  In particular, unless the implementation is clever, a very wide
> range of values can result is very large inverted arrays.

If the values can be unambiguously converted to String, using Object 
instances with empty prototype chain is recommended.  The property name 
would be the string representation of the value.  Otherwise, a Map 
implementation such as those in JSX:map.js could/should be used.
 
> The symmetric difference then looks like this:
> 
> Array.prototype.symDiff = function (a) {
>     var count = [];
>     this.forEach(function (e) { count[e] = 1; });
>     a.forEach(function (e) { count[e] = (count[e] || 0) | 2; });
>     var result = [];
>     count.forEach(function (e, i) { if (e !== 3) result.push(i); });

In most cases, you want to use a “for … in …” loop instead of 
Array.prototype.forEach(), particularly where speed is of the essence.  Not 
only can you save several function calls this way, you can also avoid 
unnecessary iterations with sparse arrays.  It should be tested before 
whether array indexes are enumerable (per ES and in recent implementations 
they are), and potentially augmented prototypes have to be considered.

Also, forEach() operates *only* on array indexes.  Therefore, the approach 
above will fail if values are not array indexes.

<http://stackoverflow.com/a/17000264/855543>

-- 
PointedEars
FAQ: <http://PointedEars.de/faq> | SVN: <http://PointedEars.de/wsvn/>
Twitter: @PointedEars2 | ES Matrix: <http://PointedEars.de/es-matrix>
Please do not Cc: me. / Bitte keine Kopien per E-Mail.

[toc] | [prev] | [next] | [standalone]

#24442

Ben Bacarisse wrote:

>     var count = [];
>     this.forEach(function (e) { count[e] = 1; });

Using “true” instead of “1” is recommended, as that will save 63 bits per 
item in the best case.


PointedEars
-- 
PointedEars
FAQ: <http://PointedEars.de/faq> | SVN: <http://PointedEars.de/wsvn/>
Twitter: @PointedEars2 | ES Matrix: <http://PointedEars.de/es-matrix>
Please do not Cc: me. / Bitte keine Kopien per E-Mail.

[toc] | [prev] | [next] | [standalone]

#24444

Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:

> Ben Bacarisse wrote:
>
>>     var count = [];
>>     this.forEach(function (e) { count[e] = 1; });
>
> Using “true” instead of “1” is recommended, as that will save 63 bits per 
> item in the best case.

But in the code I presented, true is not an option.  I could have used
two true/false arrays (at the expense of a more complex test later), but
using one array, I need at least two bits per item.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#24446

Ben Bacarisse wrote:

> Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:
>> Ben Bacarisse wrote:
>>>     var count = [];
>>>     this.forEach(function (e) { count[e] = 1; });
>>
>> Using “true” instead of “1” is recommended, as that will save 63 bits per
>> item in the best case.
> 
> But in the code I presented, true is not an option.

Why not?

-- 
PointedEars
FAQ: <http://PointedEars.de/faq> | SVN: <http://PointedEars.de/wsvn/>
Twitter: @PointedEars2 | ES Matrix: <http://PointedEars.de/es-matrix>
Please do not Cc: me. / Bitte keine Kopien per E-Mail.

[toc] | [prev] | [next] | [standalone]

#24447

Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:

> Ben Bacarisse wrote:
>
>> Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:
>>> Ben Bacarisse wrote:
>>>>     var count = [];
>>>>     this.forEach(function (e) { count[e] = 1; });
>>>
>>> Using “true” instead of “1” is recommended, as that will save 63 bits per
>>> item in the best case.
>> 
>> But in the code I presented, true is not an option.
>
> Why not?

Maybe you object to "not an option".  I should perhaps have said
confusing or unusual or some such thing.  You can use any value that
converts to 1 when used with |, but 1 is the most obvious and least
surprising of those.  (I agree that true is preferred when all you want
to do if flag membership, but that is not the case in the code I
posted.)

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#24443

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Andrew Poulos <ap_prog@hotmail.com> writes:
>
>> If I have two "simple" arrays and I need to create a third array of
>> elements that are only in one of the arrays.
<snip>
> Depending on lots of unknowns, it may be faster to invert the arrays.

As Thomas has pointed out, I was assuming that your arrays are arrays of
non-negative integers, as in your examples, but you don't say that so
it's quite possible that I've made too much of the examples.

If the arrays don't all contain values that can act as array indexes,
you can still invert the array but you can't get an array as the
result.

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#24445

Ben Bacarisse wrote:

> As Thomas has pointed out, I was assuming that your arrays are arrays of
> non-negative integers, as in your examples, but you don't say that so
> it's quite possible that I've made too much of the examples.
>  
> If the arrays don't all contain values that can act as array indexes,
> you can still invert the array but you can't get an array as the
> result.

Even if the arrays are of non-negative integers that are smaller than 2³²−1, 
a further requirement for inversion (values become keys and vice-versa) is 
uniqueness of (the string representation) of values (as can be expected from 
a set, but not an array).  Otherwise you will need a hash-table 
implementation because same original-values will map to different original-
indexes.

The upper index limit can be increased to 2⁵³−1 with jsx.array.BigArray in 
JSX:array.js.  Set and hash-table implementations can be created by reusing 
jsx.map.Map (with different Bucket setters and getters).  JSX:python.js 
contains a Set implementation (jsx.python.set [1]); the part that does not 
use Map is erroneous.

[1] <http://PointedEars.de/scripts/test/python>
-- 
PointedEars
FAQ: <http://PointedEars.de/faq> | SVN: <http://PointedEars.de/wsvn/>
Twitter: @PointedEars2 | ES Matrix: <http://PointedEars.de/es-matrix>
Please do not Cc: me. / Bitte keine Kopien per E-Mail.

[toc] | [prev] | [next] | [standalone]

#24440

Andrew Poulos wrote:

> If I have two "simple" arrays and I need to create a third array of
> elements that are only in one of the arrays. I found this
> 
> Array.prototype.difference = function (a) {
>    return this.filter(function (i) {

This returns the elements of the calling array (“this”)…

>      return !(a.indexOf(i) > -1);

… that are *not* in the array referred to by “a” (“a”).  “i” is the value of 
the respective element of “this” in each call of the function.  (I would 
label it “e” for “element” instead, to avoid confusion with the index.)

If “i” is found in “a”, a.indexOf(i) returns the index of “i” in “a”.  The 
index of standard arrays is always greater than -1 as it starts with 0.

If “i” is not found in “a”, -1 is returned.  Boolean-inverting the 
expression “a.indexOf(i) > -1” thus evaluates to “true” if “a.indexOf(i) > 
-1” evaluates to “false”, that is, if “i” was not found in “a”.  Likewise, 
it evaluates to “false” if “a.indexOf(i) > -1” evaluates to “true”, that is, 
if “i” was found in “a”. 

>    });
> };
> 
> which I don't fully understand but the issue with it that I have is that
> I need to run it on both arrays to get all the differences. For example
> 
> var arrX = [1, 2, 4, 6, 8],
>      arrY = [4, 8, 9];
> 
> var arrRes1 = arrX.difference(arrY)); // 1,2,6
> var arrRes2 = arrY.difference(arrX)); // 9
> 
> var arrRes = arrRes1.concat(arrRes2); // 1,2,6,9

There may be elements in array #1 that are not in array #2; for example, 
array #1 contains 1, 2 and 6 here which are not in array #2.  Those are 
obtained if you run “difference()” on array #1 and pass array #2.

There may also be elements in array #2 that are not in array #1; for 
example, array #2 contains 9 here which is not in array #1.  Those are 
obtained if you run the method on array #2 and pass array #1.

Logic (set theory) dictates that the elements of the sets A an B that are 
either in A or in B (which *you* call the “differences” between A and B) can 
be obtained by the union {A ∖ B} ∪ {B ∖ A} [{A \ B} U {B \ A} from here]:

                 A  \ B

             ,-'''''..'''''.
            :/1////:4 :     :
          A :///2//: 8:  9  : B
            ://///6:  :     :
             '._____''____.'


                 B  \ A

             ,-'''''..'''''.
            : 1    :4 ://///:
          A :   2  : 8://9//: B
            :     6:  ://///:
             '._____''____.'


            {A \ B} U {B \ A}

             ,-'''''..'''''.
            :/1////:4 ://///:
          A :///2//: 8://9//: B
            ://///6:  ://///:
             '._____''____.'

HTH

-- 
PointedEars
FAQ: <http://PointedEars.de/faq> | SVN: <http://PointedEars.de/wsvn/>
Twitter: @PointedEars2 | ES Matrix: <http://PointedEars.de/es-matrix>
Please do not Cc: me. / Bitte keine Kopien per E-Mail.

[toc] | [prev] | [next] | [standalone]

#24461

In comp.lang.javascript message <z_ydnZKbtslwbR7OnZ2dnUVZ_rGdnZ2d@westne
t.com.au>, Tue, 27 May 2014 11:55:03, Andrew Poulos
<ap_prog@hotmail.com> posted:

>If I have two "simple" arrays and I need to create a third array of
>elements that are only in one of the arrays.

Grammar!!  The "then" part is missing.

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.

-- 
 (c) John Stockton, nr London UK        Reply address via Merlyn Home Page.
   news:comp.lang.javascript FAQ <http://www.jibbering.com/faq/index.html>.
   <http://www.merlyn.demon.co.uk/js-index.htm> jscr maths, dates, sources.
   <http://www.merlyn.demon.co.uk/> TP/BP/Delphi/jscr/&c, FAQ items, links.

[toc] | [prev] | [next] | [standalone]

#24500

In comp.lang.javascript message <If-20140529212617@ram.dialup.fu-
berlin.de>, Thu, 29 May 2014 19:26:48, Stefan Ram <ram@zedat.fu-
berlin.de> posted:

>Dr J R Stockton <reply1400@merlyn.demon.co.uk.invalid> writes:
>>>If I have two "simple" arrays and I need to create a third array of
>>>elements that are only in one of the arrays.
>>Grammar!!  The "then" part is missing.
>
>  A sentence starting with ›If‹ does not necessarily require
>  an apodosis. It also can express a wish, but then it would
>  require a past tense or a conditional (›If I could but see
>  her again!‹ [Austen], ›If only she had her mother with her.‹
>  [Conrad]).

Accepted.  But that sentence needs one, or decapitation.

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

[toc] | [prev] | [next] | [standalone]

#24512

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

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.javascript

csiph-web