MathGroup Archive 2001

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

Search the Archive

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





  • Prev by Date: Re: Rijndael
  • Next by Date: Re: weibull distribution
  • Previous by thread: Re: Finding variables in a very long expression