[urisagit/Sort-Maker.git] / slides / slides / slide-0110.html

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML>
<HEAD>
<TITLE> Schwartian Transform (ST) Sort </TITLE>
</HEAD>
<H3 ALIGN=CENTER>1.10:  Schwartian Transform (ST) Sort </H3>
<TABLE ALIGN="CENTER" BORDER=0 WIDTH="95%">
  <TR>
    <TD WIDTH="25%" ALIGN="LEFT">
	<A HREF="slide-0109.html">Prev</A>
	<A HREF="slide-0111.html">Next</A>
	<A HREF="index.html">Index</A>
    <TD ALIGN="CENTER">
	Sort::Maker
    <TD WIDTH="25%" ALIGN="RIGHT">Page 10/12
  </TR>
</TABLE>
<HR WIDTH="95%">
<UL>
<li> Caches extracted keys in an anonymous array for each input record

<li> Stores the record itself in slot 0 of the array

<li> Uses the map/sort/map idiom

<li> Popularized by Randal Schwartz

<li> Good for medium to large sort sets

<li> Key extraction is O( N )

<li> Does a full callback to Perl in the comparison block

<li> Pass 'ST' option to make_sorter
<PRE>sub {
        map $_-&gt;[0],
        sort {
        $a-&gt;[1] cmp $b-&gt;[1]
                ||
        $a-&gt;[2] cmp $b-&gt;[2]

        }
        map [ $_,
                do{ my ($val) = $_-&gt;[0] ; $val },
                do{ my ($val) = $_-&gt;[1] ; $val }
        ], @_  ;
}

</PRE></UL>
<HR WIDTH="95%">
<TABLE ALIGN="CENTER" BORDER=0 WIDTH="95%">
  <TR>
    <TD WIDTH="30%" ALIGN="LEFT">
	<A HREF="slide-0109.html">Prev</A>
	<A HREF="slide-0111.html">Next</A>
	<A HREF="index.html">Index</A>
    <TD ALIGN="CENTER">
	YAPC::NA 2004, Buffalo, NY
    <TD WIDTH="25%" ALIGN="RIGHT">Page 10/12
  </TR>

  <TR>
    <TD ALIGN="CENTER" COLSPAN="3">
	<FONT SIZE="-3">&copy; 2004 Uri Guttman</FONT>
  </TR>

</TABLE>
</HTML>
Commit	Line	Data
7468c584	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 $_->[0],
	37	sort {
	38	$a->[1] cmp $b->[1]
	39	\|\|
	40	$a->[2] cmp $b->[2]
	41
	42	}
	43	map [ $_,
	44	do{ my ($val) = $_->[0] ; $val },
	45	do{ my ($val) = $_->[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">© 2004 Uri Guttman</FONT>
65	</TR>
66
67	</TABLE>
68	</HTML>