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

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML>
<HEAD>
<TITLE> Sort Styles </TITLE>
</HEAD>
<H3 ALIGN=CENTER>1.7:  Sort Styles </H3>
<TABLE ALIGN="CENTER" BORDER=0 WIDTH="95%">
  <TR>
    <TD WIDTH="25%" ALIGN="LEFT">
	<A HREF="slide-0106.html">Prev</A>
	<A HREF="slide-0108.html">Next</A>
	<A HREF="index.html">Index</A>
    <TD ALIGN="CENTER">
	Sort::Maker
    <TD WIDTH="25%" ALIGN="RIGHT">Page 7/12
  </TR>
</TABLE>
<HR WIDTH="95%">
<UL>
<li> Four different sorting styles to choose from

<UL>
<li> Plain

</UL>
<UL>
<li> Orcish Manouvre

</UL>
<UL>
<li> Schwartian Transform (ST)

</UL>
<UL>
<li> Guttman-Rosler Transform (GRT)

</UL>
<li> Each has its uses and advantages

<li> Styles are really different ways to cache extracted keys

<li> Caching keys moves key extraction from O( N log N ) to O( N )

<li> In larger sizes of sort sets, caching keys is a very big win

<li> This is a classic sort of arrays of numbers

<UL>
<li> Compare this code to the generated code for the different sort styles

</UL>
<PRE>
	sort { $a-&gt;[0] cmp $b-&gt;[0] ||
	       $a-&gt;[1] cmp $b-&gt;[1]
	}

</PRE></UL>
<HR WIDTH="95%">
<TABLE ALIGN="CENTER" BORDER=0 WIDTH="95%">
  <TR>
    <TD WIDTH="30%" ALIGN="LEFT">
	<A HREF="slide-0106.html">Prev</A>
	<A HREF="slide-0108.html">Next</A>
	<A HREF="index.html">Index</A>
    <TD ALIGN="CENTER">
	YAPC::NA 2004, Buffalo, NY
    <TD WIDTH="25%" ALIGN="RIGHT">Page 7/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> Sort Styles </TITLE>
	5	</HEAD>
	6	<H3 ALIGN=CENTER>1.7: Sort Styles </H3>
	7	<TABLE ALIGN="CENTER" BORDER=0 WIDTH="95%">
	8	<TR>
	9	<TD WIDTH="25%" ALIGN="LEFT">
	10	<A HREF="slide-0106.html">Prev</A>
	11	<A HREF="slide-0108.html">Next</A>
	12	<A HREF="index.html">Index</A>
	13	<TD ALIGN="CENTER">
	14	Sort::Maker
	15	<TD WIDTH="25%" ALIGN="RIGHT">Page 7/12
	16	</TR>
	17	</TABLE>
	18	<HR WIDTH="95%">
	19	<UL>
	20	<li> Four different sorting styles to choose from
	21
	22	<UL>
	23	<li> Plain
	24
	25	</UL>
	26	<UL>
	27	<li> Orcish Manouvre
	28
	29	</UL>
	30	<UL>
	31	<li> Schwartian Transform (ST)
	32
	33	</UL>
	34	<UL>
	35	<li> Guttman-Rosler Transform (GRT)
	36
	37	</UL>
	38	<li> Each has its uses and advantages
	39
	40	<li> Styles are really different ways to cache extracted keys
	41
	42	<li> Caching keys moves key extraction from O( N log N ) to O( N )
	43
	44	<li> In larger sizes of sort sets, caching keys is a very big win
	45
	46	<li> This is a classic sort of arrays of numbers
	47
	48	<UL>
	49	<li> Compare this code to the generated code for the different sort styles
	50
	51	</UL>
	52	<PRE>
	53	sort { $a->[0] cmp $b->[0] \|\|
	54	$a->[1] cmp $b->[1]
	55	}
	56
	57	</PRE></UL>
	58	<HR WIDTH="95%">
	59	<TABLE ALIGN="CENTER" BORDER=0 WIDTH="95%">
	60	<TR>
	61	<TD WIDTH="30%" ALIGN="LEFT">
	62	<A HREF="slide-0106.html">Prev</A>
	63	<A HREF="slide-0108.html">Next</A>
	64	<A HREF="index.html">Index</A>
65	<TD ALIGN="CENTER">
66	YAPC::NA 2004, Buffalo, NY
67	<TD WIDTH="25%" ALIGN="RIGHT">Page 7/12
68	</TR>
69
70	<TR>
71	<TD ALIGN="CENTER" COLSPAN="3">
72	<FONT SIZE="-3">© 2004 Uri Guttman</FONT>
73	</TR>
74
75	</TABLE>
76	</HTML>