slides/slides/slide-0110.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
   2 <HTML>
   3 <HEAD>
   4 <TITLE> Schwartian Transform (ST) Sort </TITLE>
   5 </HEAD>
   6 <H3 ALIGN=CENTER>1.10:  Schwartian Transform (ST) Sort </H3>
   7 <TABLE ALIGN="CENTER" BORDER=0 WIDTH="95%">
   8   <TR>
   9     <TD WIDTH="25%" ALIGN="LEFT">
  10         <A HREF="slide-0109.html">Prev</A>
  11         <A HREF="slide-0111.html">Next</A>
  12         <A HREF="index.html">Index</A>
  13     <TD ALIGN="CENTER">
  14         Sort::Maker
  15     <TD WIDTH="25%" ALIGN="RIGHT">Page 10/12
  16   </TR>
  17 </TABLE>
  18 <HR WIDTH="95%">
  19 <UL>
  20 <li> Caches extracted keys in an anonymous array for each input record
  21
  22 <li> Stores the record itself in slot 0 of the array
  23
  24 <li> Uses the map/sort/map idiom
  25
  26 <li> Popularized by Randal Schwartz
  27
  28 <li> Good for medium to large sort sets
  29
  30 <li> Key extraction is O( N )
  31
  32 <li> Does a full callback to Perl in the comparison block
  33
  34 <li> Pass 'ST' option to make_sorter
  35 <PRE>sub {
  36         map $_-&gt;[0],
  37         sort {
  38         $a-&gt;[1] cmp $b-&gt;[1]
  39                 ||
  40         $a-&gt;[2] cmp $b-&gt;[2]
  41
  42         }
  43         map [ $_,
  44                 do{ my ($val) = $_-&gt;[0] ; $val },
  45                 do{ my ($val) = $_-&gt;[1] ; $val }
  46         ], @_  ;
  47 }
  48
  49 </PRE></UL>
  50 <HR WIDTH="95%">
  51 <TABLE ALIGN="CENTER" BORDER=0 WIDTH="95%">
  52   <TR>
  53     <TD WIDTH="30%" ALIGN="LEFT">
  54         <A HREF="slide-0109.html">Prev</A>
  55         <A HREF="slide-0111.html">Next</A>
  56         <A HREF="index.html">Index</A>
  57     <TD ALIGN="CENTER">
  58         YAPC::NA 2004, Buffalo, NY
  59     <TD WIDTH="25%" ALIGN="RIGHT">Page 10/12
  60   </TR>
  61
  62   <TR>
  63     <TD ALIGN="CENTER" COLSPAN="3">
  64         <FONT SIZE="-3">&copy; 2004 Uri Guttman</FONT>
  65   </TR>
  66
  67 </TABLE>
  68 </HTML>