Subject: Re: [xsl] Re: Re: reverse() template (Was: RE: XSL output method="text" and indent preservation) From: Dimitre Novatchev <dnovatchev@xxxxxxxxx> Date: Sun, 5 Aug 2001 11:43:13 -0700 (PDT) |
--- Jeni Tennison <mail@xxxxxxxxxxxxxxxx> wrote: > Hi Francis, > > >> I compared the speed of the two kinds of transformations on an > >> 350MHz 64MB RAM Pentium, doubling the string length from 100 to > >> 3200. > >> > > So the least-recursion algorithm is way faster for large inputs - > > worth remembering in a functional programming environment. > > It's also interesting to compare the templates with a tail-recursive > approach, such as: > > <xsl:template name="reverse3"> > <xsl:param name="theString" /> > <xsl:param name="reversedString" /> > <xsl:choose> > <xsl:when test="$theString"> > <xsl:call-template name="reverse3"> > <xsl:with-param name="theString" > select="substring($theString, 2)" /> > <xsl:with-param name="reversedString" > select="concat(substring($theString, 1, 1), > $reversedString)" /> > </xsl:call-template> > </xsl:when> > <xsl:otherwise> > <xsl:value-of select="$reversedString" /> > </xsl:otherwise> > </xsl:choose> > </xsl:template> > > I compared times from the three templates on a 800MHz 128Mb RAM > Pentium, running each test 10 times, averaging the times reported by > MSXML run from the command line, and rounding to the nearest > millisecond. Here are the results: > > Length Simple Least Recursive Tail Recursive > ------------------------------------------------------------------ > 100 22 36 5 > 200 41 61 11 > 400 95 124 24 > 800 241 249 77 > 1600 650 485 220 > 3200 3465 975 1369 > > The tail recursive template is always substantially faster than the > simple algorithm, but it suffers from the same problem in the end - > the time taken increases exponentially rather than linearly based on > the length of the string, so for really long strings the least > recursive algorithm works best. I haven't taken detailed timings, but > there's a similar pattern in Saxon (although Saxon bugs out with the > simple algorithm and long strings, I guess a stack overflow). A > processor that doesn't optimise tail recursion would probably have > similar performance from both the simple and tail-recursive templates. > > Cheers, > > Jeni > > --- > Jeni Tennison > http://www.jenitennison.com/ > I added Jeni's algorithm and one more (6400 long) string, and timed all three templates with both MSXML3 and Saxon. The two tables below summarize the results. As it can be seen, these results are similar to my previous results and to Jeni's. I cannot explain the non-linear performance of the tail-recursive algorithm under Saxon, because as we know Saxon optimises tail-recursion implementing it using iteration. Based on these empirical results, then the following will be the "optimal" algorithm: <xsl:template name="reverse"> <xsl:param name="theString"/> <xsl:choose> <xsl:when test="string-length($theString) > 1600"> <xsl:call-template name="lrReverse"> <xsl:with-param name="theString" select="$theString"/> </xsl:call-template> </xsl:when> <xsl:otherwise> <xsl:call-template name="trReverse"> <xsl:with-param name="theString" select="$theString"/> <xsl:with-param name="reversedString" select="''"/> </xsl:call-template> </xsl:otherwise> </xsl:choose> </xsl:template> The tail-recursive and least-recursive templates will have to be modified, so that they call not themselves, but the above "reverse" template, which actually acts as a dispatcher: <xsl:template name="lrReverse"> <xsl:param name="theString"/> <xsl:variable name="thisLength" select="string-length($theString)"/> <xsl:choose> <xsl:when test="$thisLength = 1"> <xsl:value-of select="$theString"/> </xsl:when> <xsl:otherwise> <xsl:variable name="length1" select="floor($thisLength div 2)"/> <xsl:variable name="reverse1"> <xsl:call-template name="reverse"> <xsl:with-param name="theString" select="substring($theString, 1, $length1)"/> </xsl:call-template> </xsl:variable> <xsl:variable name="reverse2"> <xsl:call-template name="reverse"> <xsl:with-param name="theString" select="substring($theString, $length1+1, $thisLength - $length1 )"/> </xsl:call-template> </xsl:variable> <xsl:value-of select="concat($reverse2, $reverse1)"/> </xsl:otherwise> </xsl:choose> </xsl:template> <xsl:template name="trReverse"> <xsl:param name="theString" /> <xsl:param name="reversedString" /> <xsl:choose> <xsl:when test="$theString"> <xsl:call-template name="trReverse"> <xsl:with-param name="theString" select="substring($theString, 2)" /> <xsl:with-param name="reversedString" select="concat(substring($theString, 1, 1), $reversedString)" /> </xsl:call-template> </xsl:when> <xsl:otherwise> <xsl:value-of select="$reversedString" /> </xsl:otherwise> </xsl:choose> </xsl:template> Here are the timings tables: MSXML3 ------ Length Simple Least Recursive Tail-Recursive ------------------------------------------------------------ 100 37 58 9.5 200 85 117 24.7 400 199 235 63 800 522 469 197 1600 1460 927 613 3200 35000 1870 2198 6400 193703 3760 16000 Saxon ------ Length Simple Least Recursive Tail-Recursive ------------------------------------------------------------ 100 360 550 240 200 450 641 280 400 705 711 375 800 1392 951 641 1600 Out of memory Error 1512 1655 3200 Out of memory Error 2714 5570 6400 Out of memory Error 5250 21000 Cheers, Dimitre Novatchev. __________________________________________________ Do You Yahoo!? Make international calls for as low as $.04/minute with Yahoo! Messenger http://phonecard.yahoo.com/ XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] Re: Re: reverse() templat, Jeni Tennison | Thread | [xsl] Exclude result prefixes, David Morris |
RE: [xsl] Exclude result prefixes, David Morris | Date | [xsl] Free TrAX Poster, Roger L. Cauvin |
Month |