[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