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: Jeni Tennison <mail at jenitennison dot com>, Francis Norton <francis at redrice dot com>
- Subject: Re: [xsl] Re: Re: reverse() template (Was: RE: XSL output method="text" and indent preservation)
- From: Dimitre Novatchev <dnovatchev at yahoo dot com>
- Date: Sun, 5 Aug 2001 11:43:13 -0700 (PDT)
- Cc: xsl-list at lists dot mulberrytech dot com
- Reply-To: xsl-list at lists dot mulberrytech dot com
--- Jeni Tennison <mail@jenitennison.com> 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