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

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML>
<HEAD>
<TITLE> Orcish Manouvre Sort </TITLE>
</HEAD>
<H3 ALIGN=CENTER>1.9:  Orcish Manouvre Sort </H3>
<TABLE ALIGN="CENTER" BORDER=0 WIDTH="95%">
  <TR>
    <TD WIDTH="25%" ALIGN="LEFT">
	<A HREF="slide-0108.html">Prev</A>
	<A HREF="slide-0110.html">Next</A>
	<A HREF="index.html">Index</A>
    <TD ALIGN="CENTER">
	Sort::Maker
    <TD WIDTH="25%" ALIGN="RIGHT">Page 9/12
  </TR>
</TABLE>
<HR WIDTH="95%">
<UL>
<li> Caches extracted keys in a hash

<li> Assignments to the hash in ||=

<li> Called the orchish because of Or-Cache

<li> Created by Joseph Hall

<li> It will re-extract keys for any record with a false value

<li> The caching hash must be cleared beforehand

<UL>
<li> Sort::Maker declares a caching hash in the anonymous sub

</UL>
<li> Hash lookups are still O( N log N )

<li> Good for medium sort sets

<li> Pass 'orcish' option to make_sorter
<PRE>	sub {
		my %or_cache ;


		sort {
		(
		  ( $or_cache{$a} ||=
			do{ my ($val) = map { $_-&gt;[0] } $a ; $val } )
				cmp
		  ( $or_cache{$b} ||=
			do{ my ($val) = map { $_-&gt;[0] } $b ; $val } )
		)
			||
		(
		  ( $or_cache{$a} ||=
			do{ my ($val) = map { $_-&gt;[1] } $a ; $val } )
				cmp
		  ( $or_cache{$b} ||=
			do{ my ($val) = map { $_-&gt;[1] } $b ; $val } )
		)

		} @_  ;
	}

</PRE></UL>
<HR WIDTH="95%">
<TABLE ALIGN="CENTER" BORDER=0 WIDTH="95%">
  <TR>
    <TD WIDTH="30%" ALIGN="LEFT">
	<A HREF="slide-0108.html">Prev</A>
	<A HREF="slide-0110.html">Next</A>
	<A HREF="index.html">Index</A>
    <TD ALIGN="CENTER">
	YAPC::NA 2004, Buffalo, NY
    <TD WIDTH="25%" ALIGN="RIGHT">Page 9/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> 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 { $_->[0] } $a ; $val } )
	49	cmp
	50	( $or_cache{$b} \|\|=
	51	do{ my ($val) = map { $_->[0] } $b ; $val } )
	52	)
	53	\|\|
	54	(
	55	( $or_cache{$a} \|\|=
	56	do{ my ($val) = map { $_->[1] } $a ; $val } )
	57	cmp
	58	( $or_cache{$b} \|\|=
	59	do{ my ($val) = map { $_->[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">© 2004 Uri Guttman</FONT>
81	</TR>
82
83	</TABLE>
84	</HTML>