Re: Re: easiest way to sort a list?
- To: mathgroup at smc.vnet.net
- Subject: [mg18354] Re: [mg18334] Re: easiest way to sort a list?
- From: "Andrzej Kozlowski" <andrzej at tuins.ac.jp>
- Date: Wed, 30 Jun 1999 14:13:23 -0400
- Sender: owner-wri-mathgroup at wolfram.com
The notion of "efficiency" in this type of situations is not so clear cut
since you will get quite different results in the case of long lists with
many and those with few distinct elements. Although in your example 1 comes
just ahead of 2, at the other extreme we get:
In[1]:=
OrderedUnion1[lis_]:=
Part[lis, Sort[Map[Position[lis, #][[1]] &, Union[lis]] // Flatten]]
In[2]:=
OrderedUnion[li_]:=Block[{i},
i[n_]:=(i[n]=Sequence[];n);
i /@ li]
In[3]:=
list1=Range[1000];
In[4]:=
OrderedUnion[list1];//Timing
Out[4]=
{0.15 Second, Null}
In[5]:=
OrderedUnion1[list1];//Timing
Out[5]=
{1.91667 Second, Null}
To speak of th emost efficient program in such a case one would have to come
up with a suitable concept of the "average number of repetitions". It seems
to me that with any reasonable definiton of this OrderedUnion will come out
well ahead.
--
Andrzej Kozlowski
Toyama International University
JAPAN
http://sigma.tuins.ac.jp
http://eri2.tuins.ac.jp
----------
>From: colin at tri.org.au (Colin Rose)
To: mathgroup at smc.vnet.net
>To: mathgroup at smc.vnet.net
>Subject: [mg18354] [mg18334] Re: easiest way to sort a list?
>Date: Mon, Jun 28, 1999, 4:11 AM
>
>
>> {1, 5, 3, 5, 10, 10, 1} -> {1, 5, 3, 10}
>
>
> It's interesting to compare the efficiency of the various
> solutions posted. Given a long list, say:
>
> In[1]:= lis = Table[Random[Integer, {1, 100}], {50000}];
>
> here is how they compare on speed:
>
>
> 1. Part[lis, Sort[Map[Position[lis, #][[1]] &, Union[lis]] // Flatten]]
>
> 0.416 Second
>
>
> 2. OrderedUnion[li_] := Block[{i}, i[n_] := (i[n] = Sequence[]; n); i /@
> li]
>
> 0.5 Second
>
>
> 3. RestoreOrder[subset_, list_] :=
> Last /@ Sort[{Position[list, #, {1}, 1][[1, 1]], #} & /@ subset];
> EliminateRepetition[list_List] := RestoreOrder[Union[list], list]
>
> 2.8 Second
>
>
> 4. union2[l_] := Fold[
> Flatten[If[! MemberQ[#1, #2], Append[#1, #2], #1]] &, {}, l]
>
> 9.4 Second
>
>
> and the pretty but slow pattern matching solution:
>
> 5. lis //. {a___, x_, b___, x_, c___} -> {a, x, b, c} // Timing
>
> No solution in 5 hours (stopped).
>
>
> Timings on PowerMac G3/400 with v4.
>
> Cheers
>
> Colin
>
> --
> Colin Rose
> tr(I) - Theoretical Research Institute
> __________________________________________
> colin at tri.org.au http://www.tri.org.au/