RE: how to be as efficient as Sort[list] when list is {{x1,y1},{x2,y2},...}
- To: mathgroup at smc.vnet.net
- Subject: [mg31404] RE: [mg31400] how to be as efficient as Sort[list] when list is {{x1,y1},{x2,y2},...}
- From: "David Park" <djmp at earthlink.net>
- Date: Thu, 1 Nov 2001 02:58:36 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
Matthew,
One possible method is to use the Ordering command, which sorts the indices
of the array rather than the actual array. This sorts an array of two
element sublists on the first element and is pretty fast. (I got 0.16 second
for the one element sort.)
pairedList = Table[{Random[], i}, {i, 100000}];
(order = Ordering[pairedList[[All, 1]]];
sorted = pairedList[[order]];) // Timing
{0.33 Second, Null}
Take[sorted, 5]
{{0.0000132127, 49445}, {0.0000200217, 12077}, {0.0000270524,
1841}, {0.0000281182, 15114}, {0.000055421, 57840}}
I does seem that putting in any sorting function greatly slows down Sort.
David Park
djmp at earthlink.net
http://home.earthlink.net/~djmp/
> From: Matthew D. Langston [mailto:langston at SLAC.Stanford.EDU]
To: mathgroup 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
>
>