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


Groups > comp.soft-sys.math.mathematica > #7206 > unrolled thread

Does Union[] reliably sort?

Started byMichael Stern <nycstern@gmail.com>
First post2011-12-14 11:10 +0000
Last post2011-12-20 08:08 +0000
Articles 14 — 8 participants

Back to article view | Back to comp.soft-sys.math.mathematica


Contents

  Does Union[] reliably sort? Michael Stern <nycstern@gmail.com> - 2011-12-14 11:10 +0000
    Re: Does Union[] reliably sort? David Bailey <dave@removedbailey.co.uk> - 2011-12-15 10:03 +0000
    Re: Does Union[] reliably sort? "Nasser M. Abbasi" <nma@12000.org> - 2011-12-15 10:07 +0000
    Re: reliably sort? DrMajorBob <btreat1@austin.rr.com> - 2011-12-16 11:00 +0000
    Re: reliably sort? "Nasser M. Abbasi" <nma@12000.org> - 2011-12-16 11:01 +0000
      Re: reliably sort? David Bailey <dave@removedbailey.co.uk> - 2011-12-18 09:39 +0000
    Re: reliably sort? Ulrich Arndt <ulrich.arndt@data2knowledge.de> - 2011-12-16 11:09 +0000
    Re: reliably sort? DrMajorBob <btreat1@austin.rr.com> - 2011-12-17 07:45 +0000
    Re: Does Union[] reliably sort? markholtuk <markholtuk@googlemail.com> - 2011-12-17 07:40 +0000
    Re: reliably sort? DrMajorBob <btreat1@austin.rr.com> - 2011-12-17 07:45 +0000
    Re: reliably sort? Ulrich Arndt <ulrich.arndt@data2knowledge.de> - 2011-12-17 07:47 +0000
    Re: reliably sort? DrMajorBob <btreat1@austin.rr.com> - 2011-12-17 07:52 +0000
    R: Re: reliably sort? "Sir Bob Knight" <sir.bob.knight@gmail.com> - 2011-12-18 09:36 +0000
    Re: Does Union[] reliably sort? Szabolcs <szhorvat@gmail.com> - 2011-12-20 08:08 +0000

#7206 — Does Union[] reliably sort?

FromMichael Stern <nycstern@gmail.com>
Date2011-12-14 11:10 +0000
SubjectDoes Union[] reliably sort?
Message-ID<jca06e$a35$1@smc.vnet.net>
I have noticed that if combine two lists of date/data objects using 
Union[], the result is sorted by date.

For example

In[]:= mins={{{2001, 1, 31}, 0.993268}, {{2002, 3, 31}, 1.01395}, 
{{2003, 6, 30},
   1.08647}, {{2005, 11, 30}, 1.14752}, {{2006, 9, 30},
   1.18938}, {{2007, 2, 28}, 1.19658}, {{2008, 1, 31},
   1.20432}, {{2011, 1, 31}, 1.37501}};
In[]:= maxs={{{2000, 10, 31}, 1.01816}, {{2001, 12, 31}, 1.02714}, 
{{2004, 2, 29},
    1.12702}, {{2005, 3, 31}, 1.16986}, {{2010, 10, 31}, 1.39026}};

In[]:= Union[maxs, mins]

Out[]= {{{2000, 10, 31}, 1.01816}, {{2001, 1, 31},
   0.993268}, {{2001, 12, 31}, 1.02714}, {{2002, 3, 31},
   1.01395}, {{2003, 6, 30}, 1.08647}, {{2004, 2, 29},
   1.12702}, {{2005, 3, 31}, 1.16986}, {{2005, 11, 30},
   1.14752}, {{2006, 9, 30}, 1.18938}, {{2007, 2, 28},
   1.19658}, {{2008, 1, 31}, 1.20432}, {{2010, 10, 31},
   1.39026}, {{2011, 1, 31}, 1.37501}}

Is this reliable behavior? Is there any case in which Union would /not/ 
return results that have been properly sorted by date?

Thank you,

-Michael Stern

[toc] | [next] | [standalone]


#7236

FromDavid Bailey <dave@removedbailey.co.uk>
Date2011-12-15 10:03 +0000
Message-ID<jccglg$mje$1@smc.vnet.net>
In reply to#7206
On 14/12/2011 11:10, Michael Stern wrote:
> I have noticed that if combine two lists of date/data objects using
> Union[], the result is sorted by date.
>
> For example
>
> In[]:= mins={{{2001, 1, 31}, 0.993268}, {{2002, 3, 31}, 1.01395},
> {{2003, 6, 30},
>     1.08647}, {{2005, 11, 30}, 1.14752}, {{2006, 9, 30},
>     1.18938}, {{2007, 2, 28}, 1.19658}, {{2008, 1, 31},
>     1.20432}, {{2011, 1, 31}, 1.37501}};
> In[]:= maxs={{{2000, 10, 31}, 1.01816}, {{2001, 12, 31}, 1.02714},
> {{2004, 2, 29},
>      1.12702}, {{2005, 3, 31}, 1.16986}, {{2010, 10, 31}, 1.39026}};
>
> In[]:= Union[maxs, mins]
>
> Out[]= {{{2000, 10, 31}, 1.01816}, {{2001, 1, 31},
>     0.993268}, {{2001, 12, 31}, 1.02714}, {{2002, 3, 31},
>     1.01395}, {{2003, 6, 30}, 1.08647}, {{2004, 2, 29},
>     1.12702}, {{2005, 3, 31}, 1.16986}, {{2005, 11, 30},
>     1.14752}, {{2006, 9, 30}, 1.18938}, {{2007, 2, 28},
>     1.19658}, {{2008, 1, 31}, 1.20432}, {{2010, 10, 31},
>     1.39026}, {{2011, 1, 31}, 1.37501}}
>
> Is this reliable behavior? Is there any case in which Union would /not/
> return results that have been properly sorted by date?
>
> Thank you,
>
> -Michael Stern
Sorting is part of the operation, and you can rely on the result being 
sorted.

Mathematica obviously uses the most efficient way to perform the Union 
operation, which is to sort the entire set of elements, and then perform 
a scan through the elements, discarding adjacent duplicates.

David Bailey
http://www.dbaileyconsultancy.co.uk

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


#7243

From"Nasser M. Abbasi" <nma@12000.org>
Date2011-12-15 10:07 +0000
Message-ID<jccgs6$mls$1@smc.vnet.net>
In reply to#7206
On 12/14/2011 5:10 AM, Michael Stern wrote:
> I have noticed that if combine two lists of date/data objects using
> Union[], the result is sorted by date.
>
> For example
>
> In[]:= mins={{{2001, 1, 31}, 0.993268}, {{2002, 3, 31}, 1.01395},
> {{2003, 6, 30},
>     1.08647}, {{2005, 11, 30}, 1.14752}, {{2006, 9, 30},
>     1.18938}, {{2007, 2, 28}, 1.19658}, {{2008, 1, 31},
>     1.20432}, {{2011, 1, 31}, 1.37501}};
> In[]:= maxs={{{2000, 10, 31}, 1.01816}, {{2001, 12, 31}, 1.02714},
> {{2004, 2, 29},
>      1.12702}, {{2005, 3, 31}, 1.16986}, {{2010, 10, 31}, 1.39026}};
>
> In[]:= Union[maxs, mins]
>
> Out[]= {{{2000, 10, 31}, 1.01816}, {{2001, 1, 31},
>     0.993268}, {{2001, 12, 31}, 1.02714}, {{2002, 3, 31},
>     1.01395}, {{2003, 6, 30}, 1.08647}, {{2004, 2, 29},
>     1.12702}, {{2005, 3, 31}, 1.16986}, {{2005, 11, 30},
>     1.14752}, {{2006, 9, 30}, 1.18938}, {{2007, 2, 28},
>     1.19658}, {{2008, 1, 31}, 1.20432}, {{2010, 10, 31},
>     1.39026}, {{2011, 1, 31}, 1.37501}}
>
> Is this reliable behavior? Is there any case in which Union would /not/
> return results that have been properly sorted by date?
>
> Thank you,
>
> -Michael Stern

A good question. But the Union is the set of all distinct elements
in both sets. The result is a set. And a set has no implied order
between its elements.

It is not a sequence. Hence any order you get is just as good
as any other. So, you can't really ask about 'sorting' when it
comes to a 'set', because the question does not even apply.

I do not know why M returns the Union set sorted. But because
any order would just be as good as the other, may be it is just
being nice?

But you should not depend on the set returned having any
specific order.

You could always shuffle the set returned if you do not
like it being sorted. Quick look at the help does not show
an option to Union to remove this 'sorted' feature, but
it is easy to shuffle the set if needed.

--Nasser

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


#7268 — Re: reliably sort?

FromDrMajorBob <btreat1@austin.rr.com>
Date2011-12-16 11:00 +0000
SubjectRe: reliably sort?
Message-ID<jcf8d0$6ue$1@smc.vnet.net>
In reply to#7206
Michael,

Sorry, but no. Union always sorts.

Bobby

On Thu, 15 Dec 2011 03:56:35 -0600, Nasser M. Abbasi <nma@12000.org> wrote:

> On 12/14/2011 5:10 AM, Michael Stern wrote:
>> I have noticed that if combine two lists of date/data objects using
>> Union[], the result is sorted by date.
>>
>> For example
>>
>> In[]:= mins={{{2001, 1, 31}, 0.993268}, {{2002, 3, 31}, 1.01395},
>> {{2003, 6, 30},
>>     1.08647}, {{2005, 11, 30}, 1.14752}, {{2006, 9, 30},
>>     1.18938}, {{2007, 2, 28}, 1.19658}, {{2008, 1, 31},
>>     1.20432}, {{2011, 1, 31}, 1.37501}};
>> In[]:= maxs={{{2000, 10, 31}, 1.01816}, {{2001, 12, 31}, 1.02714},
>> {{2004, 2, 29},
>>      1.12702}, {{2005, 3, 31}, 1.16986}, {{2010, 10, 31}, 1.39026}};
>>
>> In[]:= Union[maxs, mins]
>>
>> Out[]= {{{2000, 10, 31}, 1.01816}, {{2001, 1, 31},
>>     0.993268}, {{2001, 12, 31}, 1.02714}, {{2002, 3, 31},
>>     1.01395}, {{2003, 6, 30}, 1.08647}, {{2004, 2, 29},
>>     1.12702}, {{2005, 3, 31}, 1.16986}, {{2005, 11, 30},
>>     1.14752}, {{2006, 9, 30}, 1.18938}, {{2007, 2, 28},
>>     1.19658}, {{2008, 1, 31}, 1.20432}, {{2010, 10, 31},
>>     1.39026}, {{2011, 1, 31}, 1.37501}}
>>
>> Is this reliable behavior? Is there any case in which Union would /not/
>> return results that have been properly sorted by date?
>>
>> Thank you,
>>
>> -Michael Stern
>
> A good question. But the Union is the set of all distinct elements
> in both sets. The result is a set. And a set has no implied order
> between its elements.
>
> It is not a sequence. Hence any order you get is just as good
> as any other. So, you can't really ask about 'sorting' when it
> comes to a 'set', because the question does not even apply.
>
> I do not know why M returns the Union set sorted. But because
> any order would just be as good as the other, may be it is just
> being nice?
>
> But you should not depend on the set returned having any
> specific order.
>
> You could always shuffle the set returned if you do not
> like it being sorted. Quick look at the help does not show
> an option to Union to remove this 'sorted' feature, but
> it is easy to shuffle the set if needed.
>
> --Nasser
>


-- 
DrMajorBob@yahoo.com

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


#7270 — Re: reliably sort?

From"Nasser M. Abbasi" <nma@12000.org>
Date2011-12-16 11:01 +0000
SubjectRe: reliably sort?
Message-ID<jcf8et$6v2$1@smc.vnet.net>
In reply to#7206
On 12/15/2011 2:44 PM, DrMajorBob wrote:
> Michael,
>
> Sorry, but no. Union always sorts.
>
> Bobby
>

You mean Mathematica's Union[] always sorts, right? Because
at school the teacher kept telling us that a set has no
implied order between its elements. It is just a collection
of elements. But a sequence has an order.

Result of a Union is a set. Hence one can not talk about
a set being sorted.  The result is not a set then, but a
sequence, but the result of a Union should be a set.

--Nasser


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


#7330 — Re: reliably sort?

FromDavid Bailey <dave@removedbailey.co.uk>
Date2011-12-18 09:39 +0000
SubjectRe: reliably sort?
Message-ID<jckccj$1m3$1@smc.vnet.net>
In reply to#7270
On 16/12/2011 11:01, Nasser M. Abbasi wrote:
> On 12/15/2011 2:44 PM, DrMajorBob wrote:
>> Michael,
>>
>> Sorry, but no. Union always sorts.
>>
>> Bobby
>>
>
> You mean Mathematica's Union[] always sorts, right? Because
> at school the teacher kept telling us that a set has no
> implied order between its elements. It is just a collection
> of elements. But a sequence has an order.
>
> Result of a Union is a set. Hence one can not talk about
> a set being sorted.  The result is not a set then, but a
> sequence, but the result of a Union should be a set.
>
> --Nasser
>
>
>
Lists can mean many things in Mathematica:

Vectors (nested lists represent matrices or tensors)

Actual lists

Sets

Anything else you want to represent as a list

You know what any particular list means, but Mathematica doesn't care.

Mathematica functions that operate on any of these, are defined as 
operations on lists.

David Bailey
http://www.dbaileyconsultancy.co.uk

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


#7284 — Re: reliably sort?

FromUlrich Arndt <ulrich.arndt@data2knowledge.de>
Date2011-12-16 11:09 +0000
SubjectRe: reliably sort?
Message-ID<jcf8sc$72i$1@smc.vnet.net>
In reply to#7206
Union and Sort seems not naturally connected to me. Union is a set 
operation and according to the documentation it seems that the 
implementation is using some sorting...
But there are other implementations which can be used for this set 
operation which do not use sorting and seems to have some better 
performance in some cases - will clearly depend on the underlying data!

In[169]: dim = 1000000;
list = RandomChoice[Range[299], dim];
(a = Union[list]); // Timing
(b = Tally[list][[All, 1]]); // Timing
a == Sort[b]

Out[171]= {0.222803, Null}

Out[172]= {0.003932, Null}

Out[173]= True

Ulrich

Am 15.12.2011 um 10:55 schrieb David Bailey:

> On 14/12/2011 11:10, Michael Stern wrote:
>> I have noticed that if combine two lists of date/data objects using
>> Union[], the result is sorted by date.
>>
>> For example
>>
>> In[]:= mins={{{2001, 1, 31}, 0.993268}, {{2002, 3, 31}, 1.01395},
>> {{2003, 6, 30},
>>    1.08647}, {{2005, 11, 30}, 1.14752}, {{2006, 9, 30},
>>    1.18938}, {{2007, 2, 28}, 1.19658}, {{2008, 1, 31},
>>    1.20432}, {{2011, 1, 31}, 1.37501}};
>> In[]:= maxs={{{2000, 10, 31}, 1.01816}, {{2001, 12, 31}, =
1.02714},
>> {{2004, 2, 29},
>>     1.12702}, {{2005, 3, 31}, 1.16986}, {{2010, 10, 31}, 1.39026}};
>>
>> In[]:= Union[maxs, mins]
>>
>> Out[]= {{{2000, 10, 31}, 1.01816}, {{2001, 1, 31},
>>    0.993268}, {{2001, 12, 31}, 1.02714}, {{2002, 3, 31},
>>    1.01395}, {{2003, 6, 30}, 1.08647}, {{2004, 2, 29},
>>    1.12702}, {{2005, 3, 31}, 1.16986}, {{2005, 11, 30},
>>    1.14752}, {{2006, 9, 30}, 1.18938}, {{2007, 2, 28},
>>    1.19658}, {{2008, 1, 31}, 1.20432}, {{2010, 10, 31},
>>    1.39026}, {{2011, 1, 31}, 1.37501}}
>>
>> Is this reliable behavior? Is there any case in which Union would /not/
>> return results that have been properly sorted by date?
>>
>> Thank you,
>>
>> -Michael Stern
> Sorting is part of the operation, and you can rely on the result being
> sorted.
>
> Mathematica obviously uses the most efficient way to perform the Union
> operation, which is to sort the entire set of elements, and then perform
> a scan through the elements, discarding adjacent duplicates.
>
> David Bailey
> http://www.dbaileyconsultancy.co.uk
>
>

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


#7287 — Re: reliably sort?

FromDrMajorBob <btreat1@austin.rr.com>
Date2011-12-17 07:45 +0000
SubjectRe: reliably sort?
Message-ID<jchh9u$idr$1@smc.vnet.net>
In reply to#7206
> Result of a Union is a set. Hence one can not talk about
> a set being sorted.  The result is not a set then, but a
> sequence, but the result of a Union should be a set.

a) But Union results ARE sorted. Don't pretend they're not:

Union[RandomInteger[{1, 10}, 20]]

{1, 2, 3, 5, 6, 7, 8, 9}

b) Here are two examples you might not have considered:

Union[f[a, b, a]]

f[a, b]

Union[f[a, b, a], f[c, a]]

f[a, b, c]

No sets there... and not even lists.

c) At school, when he talked about sets, the MATH teacher was not talking  
about computer languages.

d) Generally, we have lists and the functions that act on them. If lists  
have no duplicates, call them sets if you WANT to, but they don't act like  
sets unless you use functions that treat them like sets. For instance,  
does Joining sets give sets???

Join[{a, b, c}, {a}]

{a, b, c, a}

Oops, no.

e) Union, Intersection, and Complement may be the only built-in functions  
that eliminate duplicates in creating outputs... and they don't have to  
have "sets" (lists without duplicates) as their arguments.

Union[List[a, b, a], List[c, a]]

{a, b, c}

f) Union, Intersection, and Complement are not implemented to take  
advantage of the special properties of sets. Union, for instance, Joins  
lists and THEN deletes duplicates. Set theoretic packages exist that do it  
differently, so that duplicates are not created in the first place.

g) Hence, I'll repeat that Mathematica has no "sets". (As distributed.)

Bobby

On Fri, 16 Dec 2011 04:49:18 -0600, Nasser M. Abbasi <nma@12000.org> wrote:

> On 12/15/2011 2:44 PM, DrMajorBob wrote:
>> Michael,
>>
>> Sorry, but no. Union always sorts.
>>
>> Bobby
>>
>
> You mean Mathematica's Union[] always sorts, right? Because
> at school the teacher kept telling us that a set has no
> implied order between its elements. It is just a collection
> of elements. But a sequence has an order.
>
> Result of a Union is a set. Hence one can not talk about
> a set being sorted.  The result is not a set then, but a
> sequence, but the result of a Union should be a set.
>
> --Nasser
>
>
>


-- 
DrMajorBob@yahoo.com

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


#7294

Frommarkholtuk <markholtuk@googlemail.com>
Date2011-12-17 07:40 +0000
Message-ID<jchh16$i9r$1@smc.vnet.net>
In reply to#7206
You can get an unsorted Union using a combination of Join and
DeleteDuplicates as follows:

In[1]:= mins = {{{2001, 1, 31}, 0.993268}, {{2002, 3, 31},
    1.01395}, {{2003, 6, 30}, 1.08647}, {{2005, 11, 30},
    1.14752}, {{2006, 9, 30}, 1.18938}, {{2007, 2, 28},
    1.19658}, {{2008, 1, 31}, 1.20432}, {{2011, 1, 31}, 1.37501}};

maxs = {{{2000, 10, 31}, 1.01816}, {{2001, 12, 31},
    1.02714}, {{2004, 2, 29}, 1.12702}, {{2005, 3, 31},
    1.16986}, {{2010, 10, 31}, 1.39026}};

uni = Union[maxs, mins]

Out[3]= {{{2000, 10, 31}, 1.01816}, {{2001, 1, 31},
  0.993268}, {{2001, 12, 31}, 1.02714}, {{2002, 3, 31},
  1.01395}, {{2003, 6, 30}, 1.08647}, {{2004, 2, 29},
  1.12702}, {{2005, 3, 31}, 1.16986}, {{2005, 11, 30},
  1.14752}, {{2006, 9, 30}, 1.18938}, {{2007, 2, 28},
  1.19658}, {{2008, 1, 31}, 1.20432}, {{2010, 10, 31},
  1.39026}, {{2011, 1, 31}, 1.37501}}

In[4]:= del = DeleteDuplicates[Join[maxs, mins]]

Out[4]= {{{2000, 10, 31}, 1.01816}, {{2001, 12, 31},
  1.02714}, {{2004, 2, 29}, 1.12702}, {{2005, 3, 31},
  1.16986}, {{2010, 10, 31}, 1.39026}, {{2001, 1, 31},
  0.993268}, {{2002, 3, 31}, 1.01395}, {{2003, 6, 30},
  1.08647}, {{2005, 11, 30}, 1.14752}, {{2006, 9, 30},
  1.18938}, {{2007, 2, 28}, 1.19658}, {{2008, 1, 31},
  1.20432}, {{2011, 1, 31}, 1.37501}}

In[5]:=uni === del

Out[5]= False

In[6]:= sortdel = Sort[del]

Out[6]= {{{2000, 10, 31}, 1.01816}, {{2001, 1, 31},
  0.993268}, {{2001, 12, 31}, 1.02714}, {{2002, 3, 31},
  1.01395}, {{2003, 6, 30}, 1.08647}, {{2004, 2, 29},
  1.12702}, {{2005, 3, 31}, 1.16986}, {{2005, 11, 30},
  1.14752}, {{2006, 9, 30}, 1.18938}, {{2007, 2, 28},
  1.19658}, {{2008, 1, 31}, 1.20432}, {{2010, 10, 31},
  1.39026}, {{2011, 1, 31}, 1.37501}}

In[7]:=uni === sortdel

Out[7]= True

Cheers,

Mark

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


#7298 — Re: reliably sort?

FromDrMajorBob <btreat1@austin.rr.com>
Date2011-12-17 07:45 +0000
SubjectRe: reliably sort?
Message-ID<jchhat$ied$1@smc.vnet.net>
In reply to#7206
Union COULD be a set operation... if sets existed in Mathematica. The  
output may LOOK like a set to you, but that's a mirage.

> But there are other implementations which can be used for this set
> operation which do not use sorting

Ah, but you DID sort b (in order to make the results equal), whereas Union  
sorted the list before eliminating duplicates.

Yes, other implementations exist that don't involve sorting... but they're  
not built-in to Mathematica, and you haven't demonstrated one.

Bobby

On Fri, 16 Dec 2011 04:54:15 -0600, Ulrich Arndt  
<ulrich.arndt@data2knowledge.de> wrote:

> Union and Sort seems not naturally connected to me. Union is a set
> operation and according to the documentation it seems that the
> implementation is using some sorting...
> But there are other implementations which can be used for this set
> operation which do not use sorting and seems to have some better
> performance in some cases - will clearly depend on the underlying data!
>
> In[169]: dim = 1000000;
> list = RandomChoice[Range[299], dim];
> (a = Union[list]); // Timing
> (b = Tally[list][[All, 1]]); // Timing
> a == Sort[b]
>
> Out[171]= {0.222803, Null}
>
> Out[172]= {0.003932, Null}
>
> Out[173]= True
>
> Ulrich
>
> Am 15.12.2011 um 10:55 schrieb David Bailey:
>
>> On 14/12/2011 11:10, Michael Stern wrote:
>>> I have noticed that if combine two lists of date/data objects using
>>> Union[], the result is sorted by date.
>>>
>>> For example
>>>
>>> In[]:= mins={{{2001, 1, 31}, 0.993268}, {{2002, 3, 31}, 1.01395},
>>> {{2003, 6, 30},
>>>    1.08647}, {{2005, 11, 30}, 1.14752}, {{2006, 9, 30},
>>>    1.18938}, {{2007, 2, 28}, 1.19658}, {{2008, 1, 31},
>>>    1.20432}, {{2011, 1, 31}, 1.37501}};
>>> In[]:= maxs={{{2000, 10, 31}, 1.01816}, {{2001, 12, 31}, =
> 1.02714},
>>> {{2004, 2, 29},
>>>     1.12702}, {{2005, 3, 31}, 1.16986}, {{2010, 10, 31}, 1.39026}};
>>>
>>> In[]:= Union[maxs, mins]
>>>
>>> Out[]= {{{2000, 10, 31}, 1.01816}, {{2001, 1, 31},
>>>    0.993268}, {{2001, 12, 31}, 1.02714}, {{2002, 3, 31},
>>>    1.01395}, {{2003, 6, 30}, 1.08647}, {{2004, 2, 29},
>>>    1.12702}, {{2005, 3, 31}, 1.16986}, {{2005, 11, 30},
>>>    1.14752}, {{2006, 9, 30}, 1.18938}, {{2007, 2, 28},
>>>    1.19658}, {{2008, 1, 31}, 1.20432}, {{2010, 10, 31},
>>>    1.39026}, {{2011, 1, 31}, 1.37501}}
>>>
>>> Is this reliable behavior? Is there any case in which Union would /not/
>>> return results that have been properly sorted by date?
>>>
>>> Thank you,
>>>
>>> -Michael Stern
>> Sorting is part of the operation, and you can rely on the result being
>> sorted.
>>
>> Mathematica obviously uses the most efficient way to perform the Union
>> operation, which is to sort the entire set of elements, and then perform
>> a scan through the elements, discarding adjacent duplicates.
>>
>> David Bailey
>> http://www.dbaileyconsultancy.co.uk
>>
>>
>
>


-- 
DrMajorBob@yahoo.com

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


#7302 — Re: reliably sort?

FromUlrich Arndt <ulrich.arndt@data2knowledge.de>
Date2011-12-17 07:47 +0000
SubjectRe: reliably sort?
Message-ID<jchhen$igd$1@smc.vnet.net>
In reply to#7206
My statement might have been a bit misleading.
I didn't expected that mathematica is offering a pure mathematica set 
concept implementation and I saw also some ways how it can be build in 
mathematica.
But Union (Esc\[ThinSpace]un\[ThinSpace]Esc:) is indicating by its 
notation a set operation and there I was wondering why the function is 
overloaded with the additional sort.
The other thing which was puzzling me was the statement of "Mathematica 
obviously uses the most efficient way to perform the Union operation, 
which is to sort the entire set of elements..." which is performance 
wise not true for all sets as shown in the example. As I learned today 
DeleteDuplicates would have been a good candidate for the Union 
Implementation...

Ulrich

Am 16.12.2011 um 19:17 schrieb DrMajorBob:

> Union COULD be a set operation... if sets existed in Mathematica. The 
output may LOOK like a set to you, but that's a mirage.
>
>> But there are other implementations which can be used for this set
>> operation which do not use sorting
>
> Ah, but you DID sort b (in order to make the results equal), whereas 
Union sorted the list before eliminating duplicates.
>
> Yes, other implementations exist that don't involve sorting... but 
they're not built-in to Mathematica, and you haven't demonstrated one.
>
> Bobby
>
> On Fri, 16 Dec 2011 04:54:15 -0600, Ulrich Arndt 
<ulrich.arndt@data2knowledge.de> wrote:
>
>> Union and Sort seems not naturally connected to me. Union is a set
>> operation and according to the documentation it seems that the
>> implementation is using some sorting...
>> But there are other implementations which can be used for this set
>> operation which do not use sorting and seems to have some better
>> performance in some cases - will clearly depend on the underlying 
data!
>>
>> In[169]: dim = 1000000;
>> list = RandomChoice[Range[299], dim];
>> (a = Union[list]); // Timing
>> (b = Tally[list][[All, 1]]); // Timing
>> a == Sort[b]
>>
>> Out[171]= {0.222803, Null}
>>
>> Out[172]= {0.003932, Null}
>>
>> Out[173]= True
>>
>> Ulrich
>>
>> Am 15.12.2011 um 10:55 schrieb David Bailey:
>>
>>> On 14/12/2011 11:10, Michael Stern wrote:
>>>> I have noticed that if combine two lists of date/data objects using
>>>> Union[], the result is sorted by date.
>>>>
>>>> For example
>>>>
>>>> In[]:= mins={{{2001, 1, 31}, 0.993268}, {{2002, 3, 31}, 
1.01395},
>>>> {{2003, 6, 30},
>>>>   1.08647}, {{2005, 11, 30}, 1.14752}, {{2006, 9, 30},
>>>>   1.18938}, {{2007, 2, 28}, 1.19658}, {{2008, 1, 31},
>>>>   1.20432}, {{2011, 1, 31}, 1.37501}};
>>>> In[]:= maxs={{{2000, 10, 31}, 1.01816}, {{2001, 12, 31}, 
>> 1.02714},
>>>> {{2004, 2, 29},
>>>>    1.12702}, {{2005, 3, 31}, 1.16986}, {{2010, 10, 31}, 1.39026}};
>>>>
>>>> In[]:= Union[maxs, mins]
>>>>
>>>> Out[]= {{{2000, 10, 31}, 1.01816}, {{2001, 1, 31},
>>>>   0.993268}, {{2001, 12, 31}, 1.02714}, {{2002, 3, 31},
>>>>   1.01395}, {{2003, 6, 30}, 1.08647}, {{2004, 2, 29},
>>>>   1.12702}, {{2005, 3, 31}, 1.16986}, {{2005, 11, 30},
>>>>   1.14752}, {{2006, 9, 30}, 1.18938}, {{2007, 2, 28},
>>>>   1.19658}, {{2008, 1, 31}, 1.20432}, {{2010, 10, 31},
>>>>   1.39026}, {{2011, 1, 31}, 1.37501}}
>>>>
>>>> Is this reliable behavior? Is there any case in which Union would 
/not/
>>>> return results that have been properly sorted by date?
>>>>
>>>> Thank you,
>>>>
>>>> -Michael Stern
>>> Sorting is part of the operation, and you can rely on the result 
being
>>> sorted.
>>>
>>> Mathematica obviously uses the most efficient way to perform the 
Union
>>> operation, which is to sort the entire set of elements, and then 
perform
>>> a scan through the elements, discarding adjacent duplicates.
>>>
>>> David Bailey
>>> http://www.dbaileyconsultancy.co.uk
>>>
>>>
>>
>>
>
>
> --
> DrMajorBob@yahoo.com




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


#7311 — Re: reliably sort?

FromDrMajorBob <btreat1@austin.rr.com>
Date2011-12-17 07:52 +0000
SubjectRe: reliably sort?
Message-ID<jchhnb$ik0$1@smc.vnet.net>
In reply to#7206
> But Union (Esc\[ThinSpace]un\[ThinSpace]Esc:) is indicating by its  
> notation a set operation

Not really. Counterexamples:

1~Plus~2

3

1~ArcTan~1

\[Pi]/4

It's just notation... not set notation.

> The other thing which was puzzling me was the statement of "Mathematica  
> obviously uses the most efficient way to perform the Union operation,  
> which is to sort the entire set of elements..."

Another poster said that (and I may have speculated the same), but I don't  
think Mathematica documentation says that.

> DeleteDuplicates would have been a good candidate for the Union  
> Implementation...

But Union sorts, and DeleteDuplicates does not. They're optimized for  
separate tasks, and I doubt either one uses the other in general.

Bobby

On Fri, 16 Dec 2011 14:04:32 -0600, Ulrich Arndt  
<ulrich.arndt@data2knowledge.de> wrote:

> My statement might have been a bit misleading.
> I didn't expected that mathematica is offering a pure mathematica set  
> concept implementation and I saw also some ways how it can be build in  
> mathematica.
> But Union (Esc\[ThinSpace]un\[ThinSpace]Esc:) is indicating by its  
> notation a set operation and there I was wondering why the function is  
> overloaded with the additional sort.
> The other thing which was puzzling me was the statement of "Mathematica  
> obviously uses the most efficient way to perform the Union operation,  
> which is to sort the entire set of elements..." which is performance  
> wise not true for all sets as shown in the example. As I learned today  
> DeleteDuplicates would have been a good candidate for the Union  
> Implementation...
>
> Ulrich
>
> Am 16.12.2011 um 19:17 schrieb DrMajorBob:
>
>> Union COULD be a set operation... if sets existed in Mathematica. The  
>> output may LOOK like a set to you, but that's a mirage.
>>
>>> But there are other implementations which can be used for this set
>>> operation which do not use sorting
>>
>> Ah, but you DID sort b (in order to make the results equal), whereas  
>> Union sorted the list before eliminating duplicates.
>>
>> Yes, other implementations exist that don't involve sorting... but  
>> they're not built-in to Mathematica, and you haven't demonstrated one.
>>
>> Bobby
>>
>> On Fri, 16 Dec 2011 04:54:15 -0600, Ulrich Arndt  
>> <ulrich.arndt@data2knowledge.de> wrote:
>>
>>> Union and Sort seems not naturally connected to me. Union is a set
>>> operation and according to the documentation it seems that the
>>> implementation is using some sorting...
>>> But there are other implementations which can be used for this set
>>> operation which do not use sorting and seems to have some better
>>> performance in some cases - will clearly depend on the underlying data!
>>>
>>> In[169]: dim = 1000000;
>>> list = RandomChoice[Range[299], dim];
>>> (a = Union[list]); // Timing
>>> (b = Tally[list][[All, 1]]); // Timing
>>> a == Sort[b]
>>>
>>> Out[171]= {0.222803, Null}
>>>
>>> Out[172]= {0.003932, Null}
>>>
>>> Out[173]= True
>>>
>>> Ulrich
>>>
>>> Am 15.12.2011 um 10:55 schrieb David Bailey:
>>>
>>>> On 14/12/2011 11:10, Michael Stern wrote:
>>>>> I have noticed that if combine two lists of date/data objects using
>>>>> Union[], the result is sorted by date.
>>>>>
>>>>> For example
>>>>>
>>>>> In[]:= mins={{{2001, 1, 31}, 0.993268}, {{2002, 3, 31}, 1.01395},
>>>>> {{2003, 6, 30},
>>>>>   1.08647}, {{2005, 11, 30}, 1.14752}, {{2006, 9, 30},
>>>>>   1.18938}, {{2007, 2, 28}, 1.19658}, {{2008, 1, 31},
>>>>>   1.20432}, {{2011, 1, 31}, 1.37501}};
>>>>> In[]:= maxs={{{2000, 10, 31}, 1.01816}, {{2001, 12, 31}, =
>>> 1.02714},
>>>>> {{2004, 2, 29},
>>>>>    1.12702}, {{2005, 3, 31}, 1.16986}, {{2010, 10, 31}, 1.39026}};
>>>>>
>>>>> In[]:= Union[maxs, mins]
>>>>>
>>>>> Out[]= {{{2000, 10, 31}, 1.01816}, {{2001, 1, 31},
>>>>>   0.993268}, {{2001, 12, 31}, 1.02714}, {{2002, 3, 31},
>>>>>   1.01395}, {{2003, 6, 30}, 1.08647}, {{2004, 2, 29},
>>>>>   1.12702}, {{2005, 3, 31}, 1.16986}, {{2005, 11, 30},
>>>>>   1.14752}, {{2006, 9, 30}, 1.18938}, {{2007, 2, 28},
>>>>>   1.19658}, {{2008, 1, 31}, 1.20432}, {{2010, 10, 31},
>>>>>   1.39026}, {{2011, 1, 31}, 1.37501}}
>>>>>
>>>>> Is this reliable behavior? Is there any case in which Union would  
>>>>> /not/
>>>>> return results that have been properly sorted by date?
>>>>>
>>>>> Thank you,
>>>>>
>>>>> -Michael Stern
>>>> Sorting is part of the operation, and you can rely on the result being
>>>> sorted.
>>>>
>>>> Mathematica obviously uses the most efficient way to perform the Union
>>>> operation, which is to sort the entire set of elements, and then  
>>>> perform
>>>> a scan through the elements, discarding adjacent duplicates.
>>>>
>>>> David Bailey
>>>> http://www.dbaileyconsultancy.co.uk
>>>>
>>>>
>>>
>>>
>>
>>
>> --
>> DrMajorBob@yahoo.com
>
>
>
>


-- 
DrMajorBob@yahoo.com

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


#7324 — R: Re: reliably sort?

From"Sir Bob Knight" <sir.bob.knight@gmail.com>
Date2011-12-18 09:36 +0000
SubjectR: Re: reliably sort?
Message-ID<jckc6q$1jb$1@smc.vnet.net>
In reply to#7206
I agree with you Ulrich,
When we use Union we are led to think we are working on sets and thus we
expect to have the result in the same order as in input. On the other hand,
the reference page of the Union function says: 
"If the Subscript[list, i] are considered as sets, Union gives their union."
(first line in the MORE INFORMATION section). Moreover, if you take a look
at the tutorial/ListsAsSets (as suggested by Shizu in ) it lists
the Union function (and some others) in the first table named "Set
theoretical functions", but, frankly, theoretical union doesn't consider
ordering results. 
Finally, just some tests from the performance point of view:

In[36]:= data = RandomInteger[{-100, 100}, {10^8}];
In[37]:= AbsoluteTiming[r = Sort[DeleteDuplicates[data]];]
Out[37]= {0.1880107, Null}

In[38]:= AbsoluteTiming[ru = Union[data];]
Out[38]= {40.0252894, Null}

In[39]:= r === ru
Out[39]= True

So, Union seems to have no reason to be used even from the performance point
of view (40 times slower than the other). If you need the "union" as set
operation use DeleteDuplicates[set], if you need a "sorted union" you can
use Sort[DeleteDuplicates[set]]

My personal opinion is that Union is correct even sorting the result,
because the reference page says that, and in general I think that if a
function behaves coherently with the documented features it works fine.
However, the documentation should be a little more accurate when speaking
about sets and union operation on sets, perhaps specifying that the sorting
of result is not part of the theoretical function.

Regards,
~roberto

-----Messaggio originale-----
Da: Ulrich Arndt [mailto:ulrich.arndt@data2knowledge.de] 
Inviato: sabato 17 dicembre 2011 08:44
A: mathgroup@smc.vnet.net
Oggetto: Re: reliably sort?

My statement might have been a bit misleading.
I didn't expected that mathematica is offering a pure mathematica set
concept implementation and I saw also some ways how it can be build in
mathematica.
But Union (Esc\[ThinSpace]un\[ThinSpace]Esc:) is indicating by its notation
a set operation and there I was wondering why the function is overloaded
with the additional sort.
The other thing which was puzzling me was the statement of "Mathematica
obviously uses the most efficient way to perform the Union operation, which
is to sort the entire set of elements..." which is performance wise not true
for all sets as shown in the example. As I learned today DeleteDuplicates
would have been a good candidate for the Union Implementation...

Ulrich

Am 16.12.2011 um 19:17 schrieb DrMajorBob:

> Union COULD be a set operation... if sets existed in Mathematica. The
output may LOOK like a set to you, but that's a mirage.
>
>> But there are other implementations which can be used for this set 
>> operation which do not use sorting
>
> Ah, but you DID sort b (in order to make the results equal), whereas
Union sorted the list before eliminating duplicates.
>
> Yes, other implementations exist that don't involve sorting... but
they're not built-in to Mathematica, and you haven't demonstrated one.
>
> Bobby
>
> On Fri, 16 Dec 2011 04:54:15 -0600, Ulrich Arndt
<ulrich.arndt@data2knowledge.de> wrote:
>
>> Union and Sort seems not naturally connected to me. Union is a set 
>> operation and according to the documentation it seems that the 
>> implementation is using some sorting...
>> But there are other implementations which can be used for this set 
>> operation which do not use sorting and seems to have some better 
>> performance in some cases - will clearly depend on the underlying
data!
>>
>> In[169]: dim = 1000000;
>> list = RandomChoice[Range[299], dim]; (a = Union[list]); // Timing (b 
>> = Tally[list][[All, 1]]); // Timing a == Sort[b]
>>
>> Out[171]= {0.222803, Null}
>>
>> Out[172]= {0.003932, Null}
>>
>> Out[173]= True
>>
>> Ulrich
>>
>> Am 15.12.2011 um 10:55 schrieb David Bailey:
>>
>>> On 14/12/2011 11:10, Michael Stern wrote:
>>>> I have noticed that if combine two lists of date/data objects using 
>>>> Union[], the result is sorted by date.
>>>>
>>>> For example
>>>>
>>>> In[]:= mins={{{2001, 1, 31}, 0.993268}, {{2002, 3, 31},
1.01395},
>>>> {{2003, 6, 30},
>>>>   1.08647}, {{2005, 11, 30}, 1.14752}, {{2006, 9, 30},
>>>>   1.18938}, {{2007, 2, 28}, 1.19658}, {{2008, 1, 31},
>>>>   1.20432}, {{2011, 1, 31}, 1.37501}}; In[]:= maxs={{{2000, 10, 
>>>> 31}, 1.01816}, {{2001, 12, 31},
>> 1.02714},
>>>> {{2004, 2, 29},
>>>>    1.12702}, {{2005, 3, 31}, 1.16986}, {{2010, 10, 31}, 1.39026}};
>>>>
>>>> In[]:= Union[maxs, mins]
>>>>
>>>> Out[]= {{{2000, 10, 31}, 1.01816}, {{2001, 1, 31},
>>>>   0.993268}, {{2001, 12, 31}, 1.02714}, {{2002, 3, 31},
>>>>   1.01395}, {{2003, 6, 30}, 1.08647}, {{2004, 2, 29},
>>>>   1.12702}, {{2005, 3, 31}, 1.16986}, {{2005, 11, 30},
>>>>   1.14752}, {{2006, 9, 30}, 1.18938}, {{2007, 2, 28},
>>>>   1.19658}, {{2008, 1, 31}, 1.20432}, {{2010, 10, 31},
>>>>   1.39026}, {{2011, 1, 31}, 1.37501}}
>>>>
>>>> Is this reliable behavior? Is there any case in which Union would
/not/
>>>> return results that have been properly sorted by date?
>>>>
>>>> Thank you,
>>>>
>>>> -Michael Stern
>>> Sorting is part of the operation, and you can rely on the result
being
>>> sorted.
>>>
>>> Mathematica obviously uses the most efficient way to perform the
Union
>>> operation, which is to sort the entire set of elements, and then
perform
>>> a scan through the elements, discarding adjacent duplicates.
>>>
>>> David Bailey
>>> http://www.dbaileyconsultancy.co.uk
>>>
>>>
>>
>>
>
>
> --
> DrMajorBob@yahoo.com





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


#7368

FromSzabolcs <szhorvat@gmail.com>
Date2011-12-20 08:08 +0000
Message-ID<jcpfp6$qhj$1@smc.vnet.net>
In reply to#7206
Union[] is guaranteed to sort in the sense that Union[data] and Sort@Union[data] will always return exactly the same thing.

[toc] | [prev] | [standalone]


Back to top | Article view | comp.soft-sys.math.mathematica


csiph-web