MathGroup Archive 1999

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Career Opportunity with Wolfram Research
  • Next by Date: [Q] BarChart & StackGraphics incompatible ?
  • Previous by thread: Re: Re: easiest way to sort a list?
  • Next by thread: Mathematica 4.0 improvements?