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/