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

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

Unique values of array

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

Contents

  Unique values of array Asen Bozhilov <asen.bozhilov@gmail.com> - 2012-11-08 05:00 -0800
    Re: Unique values of array Scott Sauyet <scott.sauyet@gmail.com> - 2012-11-08 06:10 -0800
      Re: Unique values of array Asen Bozhilov <asen.bozhilov@gmail.com> - 2012-11-08 06:26 -0800
    Re: Unique values of array Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2012-11-08 21:21 +0100
      Re: Unique values of array Asen Bozhilov <asen.bozhilov@gmail.com> - 2012-11-08 13:06 -0800
        Re: Unique values of array Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2012-11-09 02:26 +0100
    Re: Unique values of array Dr J R Stockton <reply1245@merlyn.demon.co.uk.invalid> - 2012-11-09 18:43 +0000
      Re: Unique values of array Scott Sauyet <scott.sauyet@gmail.com> - 2012-11-10 09:06 -0800
        Re: Unique values of array "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2012-11-10 20:19 +0100
          Re: Unique values of array "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2012-11-10 20:26 +0100
          Re: Unique values of array Scott Sauyet <scott.sauyet@gmail.com> - 2012-11-11 08:47 -0800
        Re: Unique values of array Dr J R Stockton <reply1245@merlyn.demon.co.uk.invalid> - 2012-11-11 16:52 +0000
          Re: Unique values of array Scott Sauyet <scott.sauyet@gmail.com> - 2012-11-12 05:10 -0800
            Re: Unique values of array Dr J R Stockton <reply1246@merlyn.demon.co.uk.invalid> - 2012-11-13 16:39 +0000
              Re: Unique values of array "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2012-11-14 10:21 +0100
              Re: Unique values of array Scott Sauyet <scott.sauyet@gmail.com> - 2012-11-14 04:32 -0800

#17080 — Unique values of array

I have seen different approach to find the unique values in array.
ECMAScript6 will come with Set constructor and this would be easy to
achieve. The problem is how optimal are the current JS solutions for
unique values. The naive approach would be, to build a hash map when
keys are the values of the array. The problem is that there is no
built-in Map and the keys are always string. This is not applicable
when array contains different types and especially objects.
Most of the JS libraries use for ordered and unordered arrays
different algorithms. If the array is sorted the complexity of unique
could bi linear, while if the array is unordered most of the js libs
use O(n^2) approach. This is the worst especially if you have to deal
with bigger unordered arrays.
The possible optimization is to use binary search tree for searching
unique values. That approach leads O(N log N) average complexity. It
is applicable for unordered arrays. In ordered arrays BST becomes an
order list and the complexity is quadratic.
I think the generic solution could be balanced binary tree. The
complexity always be O(N log N) independently of the ordering of the
array.

The speed tests are available:
<URL: http://jsperf.com/array-unique-values>

Would be interesting if you suggest other fast approach.

[toc] | [next] | [standalone]

#17081

Asen Bozhilov wrote:
> I have seen different approach to find the unique values in array.
> ECMAScript6 will come with Set constructor and this would be easy to
> achieve. The problem is how optimal are the current JS solutions for
> unique values. The naive approach would be, to build a hash map when
> keys are the values of the array. The problem is that there is no
> built-in Map and the keys are always string. This is not applicable
> when array contains different types and especially objects.
> [ ... ]
> I think the generic solution could be balanced binary tree. The
> complexity always be O(N log N) independently of the ordering of the
> array.
>
> The speed tests are available:
> <URL:http://jsperf.com/array-unique-values>

I'm probably missing something fundamental, but any binary tree would
seem to have the same issue as the hash map implementation.  Since you
need to compare with "<", you need objects that have unique `valueOf`
of `toString` values, and once you have that, you can already pretty
well do a hash map, right?

What am I missing?

  -- Scott

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

#17082

On 8 Ноем, 16:10, Scott Sauyet <scott.sau...@gmail.com> wrote:

> I'm probably missing something fundamental, but any binary tree would
> seem to have the same issue as the hash map implementation.  Since you
> need to compare with "<", you need objects that have unique `valueOf`
> of `toString` values, and once you have that, you can already pretty
> well do a hash map, right?
>
> What am I missing?

Actually you are correct. I missed that. Seems there is not a good way
to achieve it in JavaScript. I need it such a function, but I will
drop it from my project. Have to reconsider using of unique.
Thanks.

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

#17088

Asen Bozhilov wrote:

> I have seen different approach to find the unique values in array.
> ECMAScript6 will come with Set constructor and this would be easy to
> achieve.

That would be good.  Reference?

> The problem is how optimal are the current JS solutions for
> unique values. The naive approach would be, to build a hash map when
> keys are the values of the array. The problem is that there is no
> built-in Map and the keys are always string. This is not applicable
> when array contains different types and especially objects.

So you need a Map that can have objects as keys.

<http://PointedEars.de/scripts/map.js>
<http://PointedEars.de/scripts/test/map>


PointedEars
-- 
Prototype.js was written by people who don't know javascript for people
who don't know javascript. People who don't know javascript are not
the best source of advice on designing systems that use javascript.
  -- Richard Cornford, cljs, <f806at$ail$1$8300dec7@news.demon.co.uk>

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

#17091

Thomas 'PointedEars' Lahn wrote:
> Asen Bozhilov wrote:
> > I have seen different approach to find the unique values in array.
> > ECMAScript6 will come with Set constructor and this would be easy to
> > achieve.
>
> That would be good.  Reference?

See the es-wiki harmony proposals:
<http://wiki.ecmascript.org/doku.php?id=harmony:simple_maps_and_sets>

If you are interesting SpiderMonkey already has partial support of ES6
Set:
<https://developer.mozilla.org/en-US/docs/JavaScript/Reference/
Global_Objects/Set>

Also there is a working draft of ES6:
<http://wiki.ecmascript.org/doku.php?id=harmony:specification_drafts>

There are many new things, should be discussed in separate threads.


> So you need a Map that can have objects as keys.
>
> <http://PointedEars.de/scripts/map.js>
> <http://PointedEars.de/scripts/test/map>

Thanks, I will take a look at your source.

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

#17094

Asen Bozhilov wrote:

> Thomas 'PointedEars' Lahn wrote:
>> Asen Bozhilov wrote:
>> > I have seen different approach to find the unique values in array.
>> > ECMAScript6 will come with Set constructor and this would be easy to
>> > achieve.
>>
>> That would be good.  Reference?
> 
> See the es-wiki harmony proposals:
> <http://wiki.ecmascript.org/doku.php?id=harmony:simple_maps_and_sets>

ACK.

> If you are interesting SpiderMonkey already has partial support of ES6
> Set:
> <https://developer.mozilla.org/en-US/docs/JavaScript/Reference/
> Global_Objects/Set>

The Matrix has you.
 
> Also there is a working draft of ES6:
> <http://wiki.ecmascript.org/doku.php?id=harmony:specification_drafts>
> 
> There are many new things, should be discussed in separate threads.

ACK.
 
>> So you need a Map that can have objects as keys.
>>
>> <http://PointedEars.de/scripts/map.js>
>> <http://PointedEars.de/scripts/test/map>
> 
> Thanks, I will take a look at your source.

You might also want to have a look at jsx.python.set(), which now uses 
jsx.map.Map if possible (and will probably prefer using Set() above that 
later):

<http://PointedEars.de/scripts/python.js>
<http://PointedEars.de/websvn/filedetails.php?repname=JSX&path=%2Ftrunk%2Fpython.js>
<http://PointedEars.de/scripts/test/python>


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

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

#17109

In comp.lang.javascript message <f874a1da-b06c-43af-beb6-fe05c5245469@p2
2g2000vby.googlegroups.com>, Thu, 8 Nov 2012 05:00:51, Asen Bozhilov
<asen.bozhilov@gmail.com> posted:

>I have seen different approach to find the unique values in array.

The answer depends on what you mean by "find".  If the array A is
   ["a", "b", "a"]    is the answer 2, the location of the (only) unique
item, or is it "b", the value of the item?

From the answer 2, one can rapidly discover "b" - but from the answer
"b" another half-scan may on average be needed to obtain the 2.


Create an empty Object, B.

Scan through A, finding entries S = A[k].  For each, increment B[S],
taking undefined as meaning zero.  Then scan B; your value answers are
the indexes of its elements with count==1.

For position answers, instead increment B[S].count and, if B[S].Pos is
undefined set it to k.

The answers are now those B[S].Pos for which B[S].count == 1.

Or something like that.

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

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

#17134

Dr J R Stockton wrote:
> Asen Bozhilov posted:
>
>> I have seen different approach to find the unique values in array.
>
> The answer depends on what you mean by "find".  If the array A is
>    ["a", "b", "a"]    is the answer 2, the location of the (only) unique
> item, or is it "b", the value of the item?

The performance test link Asen supplied [1] makes it clear that what
he's looking for is, in this case, ["a", "b"], although quite possibly
the order of the resulting array wouldn't matter.  In other words,
he's not looking for the values which appear only once in the input
but rather one copy of each (possibly multiply occurring) value in the
input.

  -- Scott


[1] http://jsperf.com/array-unique-values

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

#17149

Scott Sauyet wrote on 10 nov 2012 in comp.lang.javascript:

> ... makes it clear that what
> he's looking for is, in this case, ["a", "b"], although quite possibly
> the order of the resulting array wouldn't matter.  In other words,
> he's not looking for the values which appear only once in the input
> but rather one copy of each (possibly multiply occurring) value in the
> input.
> 

var arr = ["a", "b", "a"];

var i, j, obj = {};

for (i in arr)
   obj[arr[i]] = 7;

for (j in obj)
   document.write(j + ',');


-- 
Evertjan.
The Netherlands.
(Please change the x'es to dots in my emailaddress)

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

#17150

Evertjan. wrote on 10 nov 2012 in comp.lang.javascript:

> Scott Sauyet wrote on 10 nov 2012 in comp.lang.javascript:
> 
>> ... makes it clear that what
>> he's looking for is, in this case, ["a", "b"], although quite possibly
>> the order of the resulting array wouldn't matter.  In other words,
>> he's not looking for the values which appear only once in the input
>> but rather one copy of each (possibly multiply occurring) value in the
>> input.
>> 
> 
> var arr = ["a", "b", "a"];
> 
> var i, j, obj = {};
> 
> for (i in arr)
>    obj[arr[i]] = 7;
> 
> for (j in obj)
>    document.write(j + ',');

Or in one loop:

var arr = ["a", "b", "a"];

var i, obj = {};

for (i in arr) {
   if (!obj[arr[i]]) 
      document.write(arr[i] + '<br>');
   obj[arr[i]] = true;
};



-- 
Evertjan.
The Netherlands.
(Please change the x'es to dots in my emailaddress)

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

#17167

Evertjan. wrote:
> Scott Sauyet wrote :
>
>> In other words,
>> he's not looking for the values which appear only once in the input
>> but rather one copy of each (possibly multiply occurring) value in the
>> input.
>
> var arr = ["a", "b", "a"];
>
> var i, j, obj = {};
>
> for (i in arr)
>    obj[arr[i]] = 7;
>
> for (j in obj)
>    document.write(j + ',');

Which works fine for scalar-valued arrays, like arrays of Strings and
Numbers.  The OP was discussing something that would work for
arbitrary typed (although presumably consistent for a single call)
values in the array.  This is what the Harmony Set and Map are
supposed to provide.  I've been discussing certain other possibilities
offline with Asen, but we've mostly discussed the best API to provide
rather than the implementations, none of which seem particularly
difficult.

But I'm a little stuck on the idea of a generic function that can
handle this without help, for reasons I described to Asen like this:

| The problem is
| that, at least in some case, when you do have `valueOf`, you would
| really want to equate values whose `valueOf()` results match.  Think
| Date objects.  Two Date objects representing the same instant should
| probably not both appear in a list of unique values, so reference
| matching might not always be the best criteria for objects.  And yet
| `valueOf` would not be universal either.  If, for instance, you
| decided to offer `valueOf` on your ComplexNumber constructor, and
| return the magnitude (which might or might not be a reasonable thing
| to do) then clearly you would not want this value to determine that
`1
| + i` and `1 - i` match, and hence only include one in the unique
| output.
|
| It's a thorny problem if you try to make a generic solution to this
| problem, and I think the right answer might simply be to create a
| number of different functions (or a functions somehow configurable
| with several different behaviors) to capture the different flavors
of
| `unique` you might want.

Asen noted that the problem I suggested with Date objects in obvious
implementation actually occurs in the SpiderMonkey implementation of
Set released in Firefox13+.

After more discussion, I suggested an API that looked something like
this:

| var uniqueNumbers = unique(arrayOfNumbers);
| var uniqueDates = unique(arrayOfDates, function(date) {
|   return +date;
| });
| var uniqueWidgets = unique(arrayOfWidgets, unique.BY_REFERENCE);
| var uniqueDoodads = unique(arrayOfDoodads, unique.BY_VALUE_OF);

The idea is that you could pass an optional second parameter to
`unique`, a function which offers a tranformation of the input object
into its unique representation.  But there would certainly be some
standard ones that might get used, and `unique` would probably be a
good place to namespace them.

  -- Scott

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

#17184

In comp.lang.javascript message <f3044be9-979c-448d-94c6-b85acd8ac102@r7
g2000vbo.googlegroups.com>, Sat, 10 Nov 2012 09:06:51, Scott Sauyet
<scott.sauyet@gmail.com> posted:

>Dr J R Stockton wrote:
>> Asen Bozhilov posted:
>>
>>> I have seen different approach to find the unique values in array.
>>
>> The answer depends on what you mean by "find".  If the array A is
>>    ["a", "b", "a"]    is the answer 2, the location of the (only) unique
>> item, or is it "b", the value of the item?
>
>The performance test link Asen supplied [1] makes it clear that what
>he's looking for is, in this case, ["a", "b"], although quite possibly
>the order of the resulting array wouldn't matter.  In other words,
>he's not looking for the values which appear only once in the input
>but rather one copy of each (possibly multiply occurring) value in the
>input.


The same approach works for that.  Fill the new object as before, and
read out all of its elements.  I fill objects in that fashion in my
<http://www.merlyn.demon.co.uk/linxchek.htm>, frequently used, and read
them in various ways, including   for (X in Object) { ... }.

-- 
(c) John Stockton, nr London UK. Mail, see homepage.  DOS 3.3, 6.20; WinXP, 7.
   Web  <http://www.merlyn.demon.co.uk/> - FAQqish topics, acronyms & links.
   PAS EXE TXT ZIP via  <http://www.merlyn.demon.co.uk/programs/00index.htm>
   My DOS  <http://www.merlyn.demon.co.uk/batfiles.htm> - also batprogs.htm.

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

#17189

Dr J R Stockton wrote:
> Scott Sauyet posted:
>> Dr J R Stockton wrote:
>>> Asen Bozhilov posted:
>
>>>> I have seen different approach to find the unique values in array.
>
>>> The answer depends on what you mean by "find".  If the array A is
>>>    ["a", "b", "a"]    is the answer 2, the location of the (only) unique
>>> item, or is it "b", the value of the item?
>
>> The performance test link Asen supplied [1] makes it clear that what
>> he's looking for is, in this case, ["a", "b"], although quite possibly
>> the order of the resulting array wouldn't matter.  In other words,
>> he's not looking for the values which appear only once in the input
>> but rather one copy of each (possibly multiply occurring) value in the
>> input.
>
> The same approach works for that.  Fill the new object as before, and
> read out all of its elements.  I fill objects in that fashion in my
> <http://www.merlyn.demon.co.uk/linxchek.htm>, frequently used, and read
> them in various ways, including   for (X in Object) { ... }.

But that will work only if the elements of the array are Strings or
Numbers.  The OP was looking for a technique that would work for
arbitrary types.

  -- Scott

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

#17212

In comp.lang.javascript message <7cc060dd-9e63-4442-9b34-98294e8ed1ba@o8
g2000yqh.googlegroups.com>, Mon, 12 Nov 2012 05:10:13, Scott Sauyet
<scott.sauyet@gmail.com> posted:

>Dr J R Stockton wrote:
>> Scott Sauyet posted:
>>> Dr J R Stockton wrote:
>>>> Asen Bozhilov posted:
>>
>>>>> I have seen different approach to find the unique values in array.
>>
>>>> The answer depends on what you mean by "find".  If the array A is
>>>>    ["a", "b", "a"]    is the answer 2, the location of the (only) unique
>>>> item, or is it "b", the value of the item?
>>
>>> The performance test link Asen supplied [1] makes it clear that what
>>> he's looking for is, in this case, ["a", "b"], although quite possibly
>>> the order of the resulting array wouldn't matter.  In other words,
>>> he's not looking for the values which appear only once in the input
>>> but rather one copy of each (possibly multiply occurring) value in the
>>> input.
>>
>> The same approach works for that.  Fill the new object as before, and
>> read out all of its elements.  I fill objects in that fashion in my
>> <http://www.merlyn.demon.co.uk/linxchek.htm>, frequently used, and read
>> them in various ways, including   for (X in Object) { ... }.
>
>But that will work only if the elements of the array are Strings or
>Numbers.  The OP was looking for a technique that would work for
>arbitrary types.

It should be possible to convert objects of arbitrary types to strings
which are identical if and only if the objects are identical.  And I
think you mean Strings xor Numbers!

But in that case one needs to consider the meaning of identical.

  W = function(A) { return A*A }
  X = function(A) { return A*A }
  Y = function(B) { return B*B }
  Z = function(B) { return B*B}

AIUI, W X Y Z are all unequal in value.  But the functions are all
essentially the same.

-- 
 (c) John Stockton, nr London UK               Reply address via 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]

#17221

Dr J R Stockton wrote on 13 nov 2012 in comp.lang.javascript:

> But in that case one needs to consider the meaning of identical.
> 
>   W = function(A) { return A*A }
>   X = function(A) { return A*A }
>   Y = function(B) { return B*B }
>   Z = function(B) { return B*B}
> 
> AIUI, W X Y Z are all unequal in value. 
> But the functions are all
> essentially the same.

Similar, not the same, 
not in the space-time continuum,
as they are not stored in the same place,
so there pointer values are different,
nor do they live the same stretch of time.

Consider "identical" in:
<http://en.wikipedia.org/wiki/Identical_particles>

.. and consider the illusion of reality 
as seen from inside those closures
<http://en.wikipedia.org/wiki/Simulation_hypothesis>

.., so perhaps such closure views relate conceptually to déjà-vu?

-- 
Evertjan.
The Netherlands.
(Please change the x'es to dots in my emailaddress)

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

#17235

Dr J R Stockton  posted:
>> Dr J R Stockton wrote:
>>> Scott Sauyet posted:

>>>> In other words, he's not looking for the values which appear only once
>>>> in the input but rather one copy of each (possibly multiply occurring)
>>>> value in the input.
>
>>> The same approach works for that.  Fill the new object as before, and
>>> read out all of its elements.  I fill objects in that fashion in my
>>> <http://www.merlyn.demon.co.uk/linxchek.htm>, frequently used, and read
>>> them in various ways, including   for (X in Object) { ... }.
>
>> But that will work only if the elements of the array are Strings or
>> Numbers.  The OP was looking for a technique that would work for
>> arbitrary types.
>
> It should be possible to convert objects of arbitrary types to strings
> which are identical if and only if the objects are identical.

That can be done, but not by a utility function that knows nothing
about the structure of your objects and what would be considered
important data versus transient or trivial data.  Somehow the API
would need to allow you a mechanism to supply this transform when
needed.  That is, in the end, what I suggested, adding an optional
parameter of a function that would transform the object into its
unique-key String (or Number) representation.  So, for instance, for
Date objects, it's quite possible that the important distinguishing
characteristic would be captured by a function which returns the
`valueOf` for the Date.  (Note that this is not how recent Firefox
versions work with the Set implementation; they will happily hold
multiple Date objects pointing to the same instant.)

>  And I think you mean Strings xor Numbers!

Yes.  One of the assumptions was that all the objects passed in the
array had a similar type.  If not, all bets are off.

> But in that case one needs to consider the meaning of identical.
>
>   W = function(A) { return A*A }
>   X = function(A) { return A*A }
>   Y = function(B) { return B*B }
>   Z = function(B) { return B*B}
>
> AIUI, W X Y Z are all unequal in value.  But the functions are all
> essentially the same.

Of course.  And Rice's Theorem [1] demonstrates that we can never
recognize all such equivalent functions.  This technique would of
course be meant for data objects of some sort, and I'm assuming that
we could eventually arrive at a rigorous definition if we really
wanted, but the basic idea would be that we probably wouldn't care
about any properties of the objects or properties of their properties,
and so on, which happen to be functions.  It's not that they couldn't
have such, but they would likely not be taken into account in
determining uniqueness.  There could well be many other properties
that we also didn't care about for these purposes.  Again, though,
we'd leave that to the user.  If they couldn't just accept the built-
in behavior (perhaps through an `A < B` test in a sort), they would
have to supply their own function that returned a key for the object
to be used for a uniqueness test.

  -- Scott

[1] http://en.wikipedia.org/wiki/Rice%27s_theorem

[toc] | [prev] | [standalone]

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

csiph-web