Re: easiest way to sort a list?
- To: mathgroup at smc.vnet.net
- Subject: [mg18334] Re: easiest way to sort a list?
- From: colin at tri.org.au (Colin Rose)
- Date: Sun, 27 Jun 1999 15:11:22 -0400
- Organization: Theoretical Research Institute
- References: <7l1e2b$e54@smc.vnet.net> <7l3k1c$gje$1@news.biwako.ne.jp>
- Sender: owner-wri-mathgroup at wolfram.com
> {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/