Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
1999
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 1999

[Date Index] [Thread Index] [Author Index]

Search the Archive

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/





  • Prev by Date: Re: "At long last, Sir, have you no shame?"
  • Next by Date: functions that memorize
  • Previous by thread: Re: RE: easiest way to sort a list?
  • Next by thread: Re: Re: Re: easiest way to sort a list?