       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:=
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:=
list1=Table[Random[Integer,{1,9}],{10000}];

In:=
OrderedUnion[list1];//Timing
Out=
{0.166667 Second, Null}

In:=
OrderedUnion1[list1];//Timing
Out=
{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:=
list2=Range;

In:=
OrderedUnion[list2];//Timing
Out=
{0.15 Second, Null}

In:=
OrderedUnion1[list2];//Timing
Out=
{0.25 Second, Null}

What's worse, on my Mac if I try to apply OrderedUnion1 to
list2=Range 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:=
OrderedUnion2[l_]:=Module[{a},Reverse[GroebnerBasis[Map[a,l]]]/.a[k_]->k]

e.g.

In:=
OrderedUnion2[{3,2,4,5,a,a,3,6,5,2,8}]
Out=
{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?