[ABE.pm] sorting an AoA
Ricardo SIGNES
rjbs-perl-abe at lists.manxome.org
Wed Jul 26 15:35:46 PDT 2006
* Walt Mankowski <waltman at pobox.com> [2006-07-26T16:20:40]
> On Wed, Jul 26, 2006 at 04:06:32PM -0400, Faber J. Fedor wrote:
> > You're right. I obviously don't understand what's going on here (that's
> > a Schwartzian transform, right?) because I thought it was returning a
> > one-dimensional array.
>
> No, it's a simple sort comparison function.
For your edification, here's a Schwartzian transform:
You have a list of numbers, and you want to sort in order of their frobitude.
Frobitude is calculated by the frobitude() routine, and is very expensive to
calculate.
This would work:
my @sorted = sort { frobitude($a) <=> $frobitude($b) } @numbers;
but it would call frobitude on each comparison, which is going to increase
quite a lot as the size of @numbers increases. Instead, you can make a new
thing to sort by keeping track of each number's frobitude.
my @numbers_with_frobs = map { [ $_, frobitude($_) ] } @numbers;
Now you have a list of arrayrefs; each araryref is a pair: number and its
frobitude.
You can sort that like this:
my @sorted_n_with_f = sort { $a->[1] <=> $b->[1] } @numbers_with_frobs;
And then you can get back to just numbers like this:
my @sorted = map { $_->[0] } @sorted_n_with_f;
This is often done in one step:
my @sorted = map { $_->[0] }
sort { $a->[1] <=> $b->[1] }
map { [ $_, frobitude($_) ] }
@numbers;
And that ("map-sort-map") is the Schwartzian transform.
--
rjbs
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://mail.pm.org/pipermail/abe-pm/attachments/20060726/ce76640d/attachment.bin
More information about the ABE-pm
mailing list