Re: how to be as efficient as Sort[list] when list is {{x1,y1},{x2,y2},...}
- To: mathgroup at smc.vnet.net
- Subject: [mg31406] Re: how to be as efficient as Sort[list] when list is {{x1,y1},{x2,y2},...}
- From: "Allan Hayes" <hay at haystack.demon.co.uk>
- Date: Sat, 3 Nov 2001 05:29:12 -0500 (EST)
- References: <9rq857$imn$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Matthew,
The function Ordering is very useful, and quick, for this kind of
computation:
(numberList = Table[Random[],{10000},{2}])//Shallow
{{0.90065,0.977224},{0.219781,0.875281},{0.0536237,0.41698},{0.515404,
0.249111},{0.0159201,0.826861},{0.345792,0.862669},{0.992748,
0.201276},{0.124282,0.362643},{0.200976,0.774558},{0.238588,
0.181295},\[LeftSkeleton]9990\[RightSkeleton]}
s1=Sort[ numberList , OrderedQ[{#1[[1]], #2[[1]]}] &];//Timing
{14.99 Second,Null}
s2=numberList[[Ordering[numberList[[All,1]]]]];//Timing
{0.11 Second,Null}
s1===s2
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
"Matthew D. Langston" <langston at SLAC.Stanford.EDU> wrote in message
news:9rq857$imn$1 at smc.vnet.net...
> How can I write an ordering function that is as efficient as the default
> function used by the Mathematica 4.1 version of Sort[]. I ultimately need
> to sort a list of values of the form {{x1,y1},{x2,y2},...} where I only
need
> to sort on the x values while maintining the pairs of values.
>
> I benchmarked a few different methods I could think of, and all of them
pale
> in comparison to the algorithm built into Mathematica 4.1.
>
> First, I generated a list of 100,000 random numbers:
>
> numberList = Table[Random[], {100000}];
> Shallow[numberList]
> {0.625332, 0.106747, 0.0539789, 0.361381, 0.669647, 0.742005, 0.765696,
> 0.10016, 0.296304, 0.200155, <<99990>>}
>
> Then I tried the sorting algorithm built into Mathematica 4.1:
>
> {sort1Time, sort1} = Sort[numberList] // Timing;
> sort1Time
> 0.22 Second
>
> Pretty darned fast. Next I tried the simplest ordering function I could
> think of, which came out to be about 2 orders of magnitude slower than the
> default algorithm:
>
> {sort2Time, sort2} = Sort[numberList, #1 < #2 &] // Timing;
> sort2Time
> 20.419 Second
>
> According to Mathematica Help, the default ordering function for Sort[] is
> OrderedQ[{#1,#2}]&, so I tried it thinking that I would get a time
> comparable to the default algorithm, but it too came out to be about 2
> orders of magnitude slower than the default algorithm:
>
> {sort3Time, sort3} = Sort[numberList, OrderedQ[{#1, #2}] &] // Timing;
> sort3Time
> 18.577 Second
>
> Can I sort a simple list of Reals any faster than this? If so, is there
> anything special I need to do when I move to my list of pairs? I am
> currently doing something like the following, which is just too slow:
>
> Sort[{{x1,y1},{x2,y2},...} , OrderedQ[{#1[[1]], #2[[1]]}] &]
>
> Thank you for pondering my questions.
>
> Regards, Matt
>
> --
> Matthew D. Langston
> SLD, Stanford Linear Accelerator Center
> langston at SLAC.Stanford.EDU
>
>
>
>