This is the mail archive of the
xsl-list@mulberrytech.com
mailing list .
Re: Re: Re: reverse() template (Was: RE: XSL output method="text" and indent preservation)
- To: Francis Norton <francis at redrice dot com>, Dimitre Novatchev <dnovatchev at yahoo dot com>
- Subject: Re: [xsl] Re: Re: reverse() template (Was: RE: XSL output method="text" and indent preservation)
- From: Jeni Tennison <mail at jenitennison dot com>
- Date: Sun, 5 Aug 2001 13:03:50 +0100
- CC: xsl-list at lists dot mulberrytech dot com
- Organization: Jeni Tennison Consulting Ltd
- References: <20010804120647.6685.qmail@web14504.mail.yahoo.com><3B6BF614.F6413E9F@redrice.com>
- Reply-To: xsl-list at lists dot mulberrytech dot com
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