slides/slides/slide-0109.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
   2 <HTML>
   3 <HEAD>
   4 <TITLE> Orcish Manouvre Sort </TITLE>
   5 </HEAD>
   6 <H3 ALIGN=CENTER>1.9:  Orcish Manouvre Sort </H3>
   7 <TABLE ALIGN="CENTER" BORDER=0 WIDTH="95%">
   8   <TR>
   9     <TD WIDTH="25%" ALIGN="LEFT">
  10         <A HREF="slide-0108.html">Prev</A>
  11         <A HREF="slide-0110.html">Next</A>
  12         <A HREF="index.html">Index</A>
  13     <TD ALIGN="CENTER">
  14         Sort::Maker
  15     <TD WIDTH="25%" ALIGN="RIGHT">Page 9/12
  16   </TR>
  17 </TABLE>
  18 <HR WIDTH="95%">
  19 <UL>
  20 <li> Caches extracted keys in a hash
  21
  22 <li> Assignments to the hash in ||=
  23
  24 <li> Called the orchish because of Or-Cache
  25
  26 <li> Created by Joseph Hall
  27
  28 <li> It will re-extract keys for any record with a false value
  29
  30 <li> The caching hash must be cleared beforehand
  31
  32 <UL>
  33 <li> Sort::Maker declares a caching hash in the anonymous sub
  34
  35 </UL>
  36 <li> Hash lookups are still O( N log N )
  37
  38 <li> Good for medium sort sets
  39
  40 <li> Pass 'orcish' option to make_sorter
  41 <PRE>   sub {
  42                 my %or_cache ;
  43
  44
  45                 sort {
  46                 (
  47                   ( $or_cache{$a} ||=
  48                         do{ my ($val) = map { $_-&gt;[0] } $a ; $val } )
  49                                 cmp
  50                   ( $or_cache{$b} ||=
  51                         do{ my ($val) = map { $_-&gt;[0] } $b ; $val } )
  52                 )
  53                         ||
  54                 (
  55                   ( $or_cache{$a} ||=
  56                         do{ my ($val) = map { $_-&gt;[1] } $a ; $val } )
  57                                 cmp
  58                   ( $or_cache{$b} ||=
  59                         do{ my ($val) = map { $_-&gt;[1] } $b ; $val } )
  60                 )
  61
  62                 } @_  ;
  63         }
  64
  65 </PRE></UL>
  66 <HR WIDTH="95%">
  67 <TABLE ALIGN="CENTER" BORDER=0 WIDTH="95%">
  68   <TR>
  69     <TD WIDTH="30%" ALIGN="LEFT">
  70         <A HREF="slide-0108.html">Prev</A>
  71         <A HREF="slide-0110.html">Next</A>
  72         <A HREF="index.html">Index</A>
  73     <TD ALIGN="CENTER">
  74         YAPC::NA 2004, Buffalo, NY
  75     <TD WIDTH="25%" ALIGN="RIGHT">Page 9/12
  76   </TR>
  77
  78   <TR>
  79     <TD ALIGN="CENTER" COLSPAN="3">
  80         <FONT SIZE="-3">&copy; 2004 Uri Guttman</FONT>
  81   </TR>
  82
  83 </TABLE>
  84 </HTML>