Re: Re: easiest way to sort a list?

*To*: mathgroup at smc.vnet.net*Subject*: [mg18353] Re: [mg18322] Re: [mg18308] easiest way to sort a list?*From*: "Andrzej Kozlowski" <andrzej at tuins.ac.jp>*Date*: Wed, 30 Jun 1999 14:13:22 -0400*Sender*: owner-wri-mathgroup at wolfram.com

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} 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. 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} -- Andrzej Kozlowski Toyama International University JAPAN http://sigma.tuins.ac.jp http://eri2.tuins.ac.jp ---------- >From: "Carl K.Woll" <carlw at fermi.phys.washington.edu> To: mathgroup at smc.vnet.net >To: mathgroup at smc.vnet.net >Subject: [mg18353] [mg18322] Re: [mg18308] easiest way to sort a list? >Date: Sun, Jun 27, 1999, 8:08 AM > > Peter, > > Here is one idea. > > OrderedUnion[li_]:=Block[{i}, > i[n_]:=(i[n]=Sequence[];n); > i /@ li] > > The first time the function i hits an integer, it returns that integer. After > that, it returns Sequence[], which disappears. I had another idea, where I > adjoined an auxiliary index list, then sorted and unioned using appropriate > tests. This idea was slightly faster for short lists. However, for longer > lists, it was slower, as the sorting algorithm is O(n log(n)), and the function > OrderedUnion is O(n). > > Carl Woll > Physics Dept > U of Washington > > Peter T. Wang wrote: > >> Hi everyone, >> >> Here's my question: Suppose you have a list of integers, not all distinct, >> say >> {1, 5, 3, 5, 10, 10, 1}, >> >> and you want to obtain the list >> >> {1, 5, 3, 10} >> >> which is the set of distinct elements but with the order preserved; i.e., >> the order in which the elements in the second list appear is the same as >> the order in which it first occurs in the first list. What is a simple >> way to do this? Evidently Union[] sorts the elements in canonical order, >> which is not desirable. My current solution is so messy that I suspect >> there must be an easier way. >> >> -peter > > >