Re: Re: easiest way to sort a list?
- To: mathgroup at smc.vnet.net
- Subject: [mg18345] Re: [mg18334] Re: easiest way to sort a list?
- From: "Carl K.Woll" <carlw at fermi.phys.washington.edu>
- Date: Wed, 30 Jun 1999 14:13:18 -0400
- Organization: Department of Physics
- References: <7l1e2b$e54@smc.vnet.net> <7l3k1c$gje$1@news.biwako.ne.jp> <199906271911.PAA19088@smc.vnet.net.>
- Sender: owner-wri-mathgroup at wolfram.com
Hi Colin,
Just after I posted my efficiency comparison, I noticed yours in my inbox. I
didn't see your first solution posted before, so I included it in my tests.
I get similar timings for random samples similar to your test case. On the
other hand, if you change the test case to something like
lis=Table[Random[Integer,{1,10000}],{20000}];
you will find that OrderedUnion will be much faster (I lowered the numbers a
little bit since my computer isn't very fast). On my computer, OrderedUnion
took 12 seconds and your first solution took 725 seconds for the above test
case. So, your first solution depends more strongly on the size of
Union[lis] than OrderedUnion does.
Carl Woll
Physics Dept
U of Washington
Colin Rose wrote:
> > {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/