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

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML>
<HEAD>
<TITLE> Guttman-Rosler Transform (GRT) Sort </TITLE>
</HEAD>
<H3 ALIGN=CENTER>1.11:  Guttman-Rosler Transform (GRT) Sort </H3>
<TABLE ALIGN="CENTER" BORDER=0 WIDTH="95%">
  <TR>
    <TD WIDTH="25%" ALIGN="LEFT">
	<A HREF="slide-0110.html">Prev</A>
	<A HREF="slide-0112.html">Next</A>
	<A HREF="index.html">Index</A>
    <TD ALIGN="CENTER">
	Sort::Maker
    <TD WIDTH="25%" ALIGN="RIGHT">Page 11/12
  </TR>
</TABLE>
<HR WIDTH="95%">
<UL>
<li> Caches extracted keys in a single string for each input record

<li> String records can be stored in that string

<li> Reference records have their index stored in the cache string

<UL>
<li> The sorted indices are used to slice into the input array to create
    sorted records

</UL>
<li> Key extraction is O( N )

<li> The comparison code is internal and uses C with no Perl callback (big
   win)

<li> More complex to use properly and efficiently

<li> GRT has special key description attributes for optimization

<UL>
<li> Numbers can be integer/float, signed/unsigned

</UL>
<UL>
<li> Strings can be fixed/varying

</UL>
<UL>
<li> Fastest sort style for larger sets of sort records

</UL>
<li> Pass 'GRT' option to make_sorter

<PRE>sub {
        my $rec_ind = 0 ;

        return  @_[
            map unpack( 'N', substr( $_, -4 ) ), 
            sort
            map pack( "Z*Z*N",
                do{ my( $val ) = $_-&gt;[0] ; ( $val ) },
                do{ my( $val ) = $_-&gt;[1] ; ( $val ) },
                $rec_ind++
            ), @_
        ] ;
}

</PRE></UL>
<HR WIDTH="95%">
<TABLE ALIGN="CENTER" BORDER=0 WIDTH="95%">
  <TR>
    <TD WIDTH="30%" ALIGN="LEFT">
	<A HREF="slide-0110.html">Prev</A>
	<A HREF="slide-0112.html">Next</A>
	<A HREF="index.html">Index</A>
    <TD ALIGN="CENTER">
	YAPC::NA 2004, Buffalo, NY
    <TD WIDTH="25%" ALIGN="RIGHT">Page 11/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> 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( "ZZN",
	61	do{ my( $val ) = $_->[0] ; ( $val ) },
	62	do{ my( $val ) = $_->[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">© 2004 Uri Guttman</FONT>
84	</TR>
85
86	</TABLE>
87	</HTML>