Re: Re: easiest way to sort a list?

*To*: mathgroup at smc.vnet.net*Subject*: [mg18401] Re: [mg18322] Re: [mg18308] easiest way to sort a list?*From*: Daniel Lichtblau <danl at wolfram.com>*Date*: Wed, 7 Jul 1999 00:11:02 -0400*Organization*: Wolfram Research, Inc.*References*: <7lccua$1gg@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

Andrzej Kozlowski wrote: > > This is very efficient indeed and beutifully illustrates the usefullnes of > the amazing Sequence function. The only slight weakness that I can see is > when dealing with very long lists with a small number of distinct elements. > Since we know that the final output must have the same number of elements as > given by the (very fast) built-in Union function, for such lists one may do > better by a code which stops checking elements of li once it has constructed > a list of length Length[Union[li]]. Here is a modified code that does this: > > In[2]:= > OrderedUnion1[li_]:=Block[{i,counter=0,l0={},m=Length[Union[li]]}, > i[n_]:=(i[n]=Sequence[];counter=counter+1;n); > Scan[If[counter<m,l0={l0,i[#]},Return[Flatten[l0]]]&,li];Flatten[l0]] > > On very long lists with a small number of distinct elements this is somewhat > faster than OrderedUnion: > > In[3]:= > list1=Table[Random[Integer,{1,9}],{10000}]; > > In[4]:= > OrderedUnion[list1];//Timing > Out[4]= > {0.166667 Second, Null} > > In[5]:= > OrderedUnion1[list1];//Timing > Out[5]= > {0.0833333 Second, Null} > > (Mac PowerBook G3 233 Mhz). > > However, in the case of lists with very few or no repetitions the balance is > naturally reversed: > > In[6]:= > list2=Range[1000]; > > In[7]:= > OrderedUnion[list2];//Timing > Out[7]= > {0.15 Second, Null} > > In[8]:= > OrderedUnion1[list2];//Timing > Out[8]= > {0.25 Second, Null} Use of Union or Sort will make the asymptotic complexity worse regardless of size of result, but the crossover may be so large when dealing with lists of machine integers or machine reals that it hardly matters, at least in version 4. I'd not be surprised if it is on the order of a few million. > What's worse, on my Mac if I try to apply OrderedUnion1 to > list2=Range[10000] I get a crash, caused presumably by the Kernel running > out of memory while building up a huge nested list. This problem was brought to my attention by Colin Rose. I need to look into it. > For those with a taste for weird Mathematica programs here is an unusual > (and unfortunately inefficient) example: > > In[10]:= > OrderedUnion2[l_]:=Module[{a},Reverse[GroebnerBasis[Map[a,l]]]/.a[k_]->k] > > e.g. > > In[11]:= > OrderedUnion2[{3,2,4,5,a,a,3,6,5,2,8}] > Out[11]= > {3, 2, 4, 5, a, 6, 8} This relies on the fact that GroebnerBasis orders its variables as they appear in the input. Not really safe to rely on this as it is not documented behavior. Specifically, default ordering is unspecified. > -- > Andrzej Kozlowski > Toyama International University > JAPAN > http://sigma.tuins.ac.jp > http://eri2.tuins.ac.jp > Daniel Lichtblau Wolfram Research PS I agree Carl Woll's method is really nice. I played around with the problem before I saw his, also had an O(n+m) method where n = size in and m = size out. His method gave timings consistently around 2/3 of mine on large problems.