SPUG: Interesting sort issue
Parr, Ryan
Ryan.Parr at wwireless.com
Wed Oct 24 11:12:07 CDT 2001
Jim,
That makes perfect sense. Thank you for the tip.
-- Ryan Parr
-----Original Message-----
From: Jim Flanagan [mailto:jimfl at colltech.com]
Sent: Wednesday, October 24, 2001 8:31 AM
To: Parr, Ryan; spug-list at pm.org
Subject: Re: SPUG: Interesting sort issue
--Also Sprache "Parr, Ryan" <Ryan.Parr at wwireless.com> On Tuesday, October
23, 2001 8:14 PM -0700:
> sub sorter {
> my $a_title = lc(FileAPI->new($a)->getTitle());
> my $b_title = lc(FileAPI->new($b)->getTitle());
>
> $a_title cmp $b_title;
> }
As a side note, this sort is making two FileAPI objects, and calling two
methods for every comparison in your sort, which, for sorting large
numbers of items could get expensive, since you end up having to compute
the lc(new->getTitle) multiple times for each element.
Ideally, you'd like to do the new()->getTitle() combo just once for
each item in the sort list.
An analogy of this process is you have 50 dogs you want to sort by
weight. The dogs don't like to be weighed, and so weighing them is a
hassle (though it's easier than cats). Each time you want to compare the
weight of two dogs to sort them, you have to weigh both of them. Order
hassle squared! So you get 50 cardboard boxes. You weigh each dog once,
put the dog in a box, and write the weight on the box. Then you sort the
boxes by the number written on the box. When those are all in order, take
the dogs out of the boxes one by one.
There's a trick called the Schwarzian Transform (named after Randall),
which you can use to do this. It looks like this:
@sorted =
map { $_->[0] }
sort { $a->[1] cmp $b->[1] }
map { [ $_, lc(FileAPI->new($_)->getTitle()) ] } @unsorted;
You sort of need to read this from the bottom up, (or the inside out).
The last line makes an array of 2-element arrayref "boxes". These contain
as the zeroth element an item from the list to be sorted, and as the oneth
element, the result of
lc(FileAPI->new()->getTitle())
on that element. The next line up sorts these "boxes" based on the oneth
element. The next line up from that extracts the zeroth element from
these boxes, and you end up with a list of the zeroth box elements sorted
based on the oneth box elements.
For a detailed, illustrated explanation of what is going on with the
Schwartzian transform, see:
http://www.5sigma.com/perl/schwtr.html
--
Jim Flanagan Collective Technologies
jimfl at colltech.com http://www.colltech.com
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
POST TO: spug-list at pm.org PROBLEMS: owner-spug-list at pm.org
Subscriptions; Email to majordomo at pm.org: ACTION LIST EMAIL
Replace ACTION by subscribe or unsubscribe, EMAIL by your Email-address
For daily traffic, use spug-list for LIST ; for weekly, spug-list-digest
Seattle Perl Users Group (SPUG) Home Page: http://zipcon.net/spug/
More information about the spug-list
mailing list