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