[ABE.pm] sorting an AoA

[Walt Mankowski]

On Wed, Jul 26, 2006 at 06:35:46PM -0400, Ricardo SIGNES wrote:
> * 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.

Right.  I should have added something like that in my post.  Thanks.

The key difference in that in Faber's example, we're sorting by a
field that's already in the list, while in Ricardo's we're sorting by
a calculated value.  The Schwartzian Transform is really just a clever
way caching the calculated values so they don't need to be
recalculated for each comparison.

Walt
-------------- 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/20060727/807403f0/attachment-0001.bin