Subject: Re: [xsl] Re: Re: reverse() template (Was: RE: XSL output method="text" and indent preservation) From: Jeni Tennison <mail@xxxxxxxxxxxxxxxx> Date: Sun, 5 Aug 2001 13:03:50 +0100 |
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/ XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: [xsl] Re: Re: reverse() templat, Francis Norton | Thread | Re: [xsl] Re: Re: reverse() templat, Dimitre Novatchev |
RE: [xsl] Exclude result prefixes, Michael Kay | Date | RE: [xsl] Exclude result prefixes, David Morris |
Month |