Services & ResourcesWolfram ForumsMathGroup Archive

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

Re: Sorting and Selecting in MultiLevel Lists?

• To: mathgroup at smc.vnet.net
• Subject: [mg31208] Re: Sorting and Selecting in MultiLevel Lists?
• From: "Allan Hayes" <hay at haystack.demon.co.uk>
• Date: Fri, 19 Oct 2001 03:11:58 -0400 (EDT)
• References: <200110140811.EAA02423@smc.vnet.net> <9qjjp9$j8c$1@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

Using Ordering instead of Sort gives a further speedup:

sortOnNorm3[ll_List] := ll[[Ordering[#.#&/@ll]]]
sortOnNorm[ll_List] := Map[Rest, Sort[Map[Prepend[#,#.#]&, ll]]]

n = 4;
ll = Table[Random[], {10^n}, {2}];

Timing[sortedll = sortOnNorm[ll];]

{1.59 Second,Null}

Timing[sortedll3 = sortOnNorm3[ll];]

{0.33 Second,Null}

sortedll===sortedll3

True

--
Allan
---------------------
Allan Hayes
Mathematica Training and Consulting
Leicester UK
www.haystack.demon.co.uk
hay at haystack.demon.co.uk
Voice: +44 (0)116 271 4198
Fax: +44 (0)870 164 0565

"Daniel Lichtblau" <danl at wolfram.com> wrote in message
news:9qjjp9$j8c$1 at smc.vnet.net...
> aes wrote:
> >
> > Suppose I want to Sort, or Select from, a multilevel list, e.g.
> >
> >         myList =  { {x1,y1},  {x2,y2},  {x3,y3}, . . . }
> >
> > with a Sort or Select criterion that's some function of the xn and yn
values
> >
> > For example, I can sort the above list on the value of x^2 + y^2 by
using
> >
> >     Sort[myList, (Take[#1, 1][[1]]^2 + Take[#1, 2][[1]]^2) <
> >                         (Take[#2, 1][[1]]^2 + Take[#2, 2][[1]]^2) &]
> >
> > Question:  Is there an easier way to get at the "x" and "y" values
associated
> > with the #1 and #2 arguments in Sort, or with the # argument in Select,
than the
> > awkward   Take[#,m][[n]]   notation used here?
>
>
> If the outer lists in question are large then speed can be an issue. In
> that case it is best to use default Sort because comparison evaluations
> for the 2-argument form are relatively expensive. To achieve this goal
> you can prepend your "sorting value" to each sublist, sort, then remove
> it.
>
> sortOnNorm[ll_List] := Map[Rest, Sort[Map[Prepend[#,#.#]&, ll]]]
>
> In[74]:= n = 5;
>
> In[75]:= ll = Table[Random[], {10^n}, {2}];
>
> In[76]:= Timing[sortedll = sortOnNorm[ll];]
> Out[76]= {0.88 Second, Null}
>
> For comparison:
>
> In[78]:= sortOnNorm2[ll_List] := Sort[ll, #1.#1 < #2.#2 &]
>
> In[79]:= Timing[sortedll2 = sortOnNorm2[ll];]
> Out[79]= {32.46 Second, Null}
>
> In[80]:= sortedll2 === sortedll
> Out[80]= True
>
>
> Daniel Lichtblau
> Wolfram Research
>

• References:
  • Sorting and Selecting in MultiLevel Lists?
    • From: aes <siegman@stanford.edu>