SPUG: Interesting sort issue

Jim Flanagan jimfl at colltech.com
Wed Oct 24 09:31:25 CDT 2001


--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