Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.soft-sys.math.mathematica > #7206 > unrolled thread
| Started by | Michael Stern <nycstern@gmail.com> |
|---|---|
| First post | 2011-12-14 11:10 +0000 |
| Last post | 2011-12-20 08:08 +0000 |
| Articles | 14 — 8 participants |
Back to article view | Back to comp.soft-sys.math.mathematica
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
| From | Michael Stern <nycstern@gmail.com> |
|---|---|
| Date | 2011-12-14 11:10 +0000 |
| Subject | Does 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]
| From | David Bailey <dave@removedbailey.co.uk> |
|---|---|
| Date | 2011-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]
| From | "Nasser M. Abbasi" <nma@12000.org> |
|---|---|
| Date | 2011-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]
| From | DrMajorBob <btreat1@austin.rr.com> |
|---|---|
| Date | 2011-12-16 11:00 +0000 |
| Subject | Re: 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]
| From | "Nasser M. Abbasi" <nma@12000.org> |
|---|---|
| Date | 2011-12-16 11:01 +0000 |
| Subject | Re: 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]
| From | David Bailey <dave@removedbailey.co.uk> |
|---|---|
| Date | 2011-12-18 09:39 +0000 |
| Subject | Re: 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]
| From | Ulrich Arndt <ulrich.arndt@data2knowledge.de> |
|---|---|
| Date | 2011-12-16 11:09 +0000 |
| Subject | Re: 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]
| From | DrMajorBob <btreat1@austin.rr.com> |
|---|---|
| Date | 2011-12-17 07:45 +0000 |
| Subject | Re: 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]
| From | markholtuk <markholtuk@googlemail.com> |
|---|---|
| Date | 2011-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]
| From | DrMajorBob <btreat1@austin.rr.com> |
|---|---|
| Date | 2011-12-17 07:45 +0000 |
| Subject | Re: 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]
| From | Ulrich Arndt <ulrich.arndt@data2knowledge.de> |
|---|---|
| Date | 2011-12-17 07:47 +0000 |
| Subject | Re: 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]
| From | DrMajorBob <btreat1@austin.rr.com> |
|---|---|
| Date | 2011-12-17 07:52 +0000 |
| Subject | Re: 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]
| From | "Sir Bob Knight" <sir.bob.knight@gmail.com> |
|---|---|
| Date | 2011-12-18 09:36 +0000 |
| Subject | R: 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]
| From | Szabolcs <szhorvat@gmail.com> |
|---|---|
| Date | 2011-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