slides/slides/slide-0111.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
   2 <HTML>
   3 <HEAD>
   4 <TITLE> Guttman-Rosler Transform (GRT) Sort </TITLE>
   5 </HEAD>
   6 <H3 ALIGN=CENTER>1.11:  Guttman-Rosler Transform (GRT) Sort </H3>
   7 <TABLE ALIGN="CENTER" BORDER=0 WIDTH="95%">
   8   <TR>
   9     <TD WIDTH="25%" ALIGN="LEFT">
  10         <A HREF="slide-0110.html">Prev</A>
  11         <A HREF="slide-0112.html">Next</A>
  12         <A HREF="index.html">Index</A>
  13     <TD ALIGN="CENTER">
  14         Sort::Maker
  15     <TD WIDTH="25%" ALIGN="RIGHT">Page 11/12
  16   </TR>
  17 </TABLE>
  18 <HR WIDTH="95%">
  19 <UL>
  20 <li> Caches extracted keys in a single string for each input record
  21
  22 <li> String records can be stored in that string
  23
  24 <li> Reference records have their index stored in the cache string
  25
  26 <UL>
  27 <li> The sorted indices are used to slice into the input array to create
  28     sorted records
  29
  30 </UL>
  31 <li> Key extraction is O( N )
  32
  33 <li> The comparison code is internal and uses C with no Perl callback (big
  34    win)
  35
  36 <li> More complex to use properly and efficiently
  37
  38 <li> GRT has special key description attributes for optimization
  39
  40 <UL>
  41 <li> Numbers can be integer/float, signed/unsigned
  42
  43 </UL>
  44 <UL>
  45 <li> Strings can be fixed/varying
  46
  47 </UL>
  48 <UL>
  49 <li> Fastest sort style for larger sets of sort records
  50
  51 </UL>
  52 <li> Pass 'GRT' option to make_sorter
  53
  54 <PRE>sub {
  55         my $rec_ind = 0 ;
  56
  57         return  @_[
  58             map unpack( 'N', substr( $_, -4 ) ),
  59             sort
  60             map pack( "Z*Z*N",
  61                 do{ my( $val ) = $_-&gt;[0] ; ( $val ) },
  62                 do{ my( $val ) = $_-&gt;[1] ; ( $val ) },
  63                 $rec_ind++
  64             ), @_
  65         ] ;
  66 }
  67
  68 </PRE></UL>
  69 <HR WIDTH="95%">
  70 <TABLE ALIGN="CENTER" BORDER=0 WIDTH="95%">
  71   <TR>
  72     <TD WIDTH="30%" ALIGN="LEFT">
  73         <A HREF="slide-0110.html">Prev</A>
  74         <A HREF="slide-0112.html">Next</A>
  75         <A HREF="index.html">Index</A>
  76     <TD ALIGN="CENTER">
  77         YAPC::NA 2004, Buffalo, NY
  78     <TD WIDTH="25%" ALIGN="RIGHT">Page 11/12
  79   </TR>
  80
  81   <TR>
  82     <TD ALIGN="CENTER" COLSPAN="3">
  83         <FONT SIZE="-3">&copy; 2004 Uri Guttman</FONT>
  84   </TR>
  85
  86 </TABLE>
  87 </HTML>