how to be as efficient as Sort[list] when list is {{x1,y1},{x2,y2},...}
- To: mathgroup at smc.vnet.net
- Subject: [mg31400] how to be as efficient as Sort[list] when list is {{x1,y1},{x2,y2},...}
- From: "Matthew D. Langston" <langston at SLAC.Stanford.EDU>
- Date: Wed, 31 Oct 2001 19:59:36 -0500 (EST)
- Organization: Stanford Linear Accelerator Center
- Sender: owner-wri-mathgroup at wolfram.com
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