This is the mail archive of the
xsl-list@mulberrytech.com
mailing list .
Re: Re: lookup-table thoughts (was Re: matching multiple times, outputting once?
Hi Tom,
> However, I think making R tail-recursive is a success only if the
> "cons" is constant-time.
The proof of the pudding is in the eating, as they say. It seems
you're right. I tried the following tail-recursive, non-tail-recursive
and divide-and-conquer templates with Saxon 6.4.4:
<xsl:template name="embedTailRecursive">
<xsl:param name="count" select="10" />
<xsl:param name="base" select="'foo'" />
<xsl:choose>
<xsl:when test="$count > 1">
<xsl:call-template name="embedTailRecursive">
<xsl:with-param name="count" select="$count - 1" />
<xsl:with-param name="base">
<foo><xsl:copy-of select="$base" /></foo>
</xsl:with-param>
</xsl:call-template>
</xsl:when>
<xsl:otherwise>
<xsl:copy-of select="$base" />
</xsl:otherwise>
</xsl:choose>
</xsl:template>
<xsl:template name="embedNotTailRecursive">
<xsl:param name="count" select="10" />
<xsl:param name="base" select="'foo'" />
<xsl:choose>
<xsl:when test="$count > 1">
<foo>
<xsl:call-template name="embedNotTailRecursive">
<xsl:with-param name="count" select="$count - 1" />
<xsl:with-param name="base" select="$base" />
</xsl:call-template>
</foo>
</xsl:when>
<xsl:otherwise>
<xsl:copy-of select="$base" />
</xsl:otherwise>
</xsl:choose>
</xsl:template>
<xsl:template name="embedDivAndConquer">
<xsl:param name="count" select="10" />
<xsl:param name="base" select="'foo'" />
<xsl:choose>
<xsl:when test="$count = 1">
<xsl:copy-of select="$base" />
</xsl:when>
<xsl:when test="not($count mod 2)">
<foo>
<xsl:call-template name="embedDivAndConquer">
<xsl:with-param name="count" select="$count div 2" />
<xsl:with-param name="base" select="$base" />
</xsl:call-template>
</foo>
<foo>
<xsl:call-template name="embedDivAndConquer">
<xsl:with-param name="count" select="$count div 2" />
<xsl:with-param name="base" select="$base" />
</xsl:call-template>
</foo>
</xsl:when>
<xsl:otherwise>
<foo><xsl:copy-of select="$base" /></foo>
<foo>
<xsl:call-template name="embedDivAndConquer">
<xsl:with-param name="count" select="($count - 1) div 2" />
<xsl:with-param name="base" select="$base" />
</xsl:call-template>
</foo>
<foo>
<xsl:call-template name="embedDivAndConquer">
<xsl:with-param name="count" select="($count - 1) div 2" />
<xsl:with-param name="base" select="$base" />
</xsl:call-template>
</foo>
</xsl:otherwise>
</xsl:choose>
</xsl:template>
The timings were as follows:
count Tail Recursive Not Tail Recursive Divide And Conquer
10 388 393 396
50 429 396 396
100 451 403 401
200 611 418 403
500 2666 654 423
1000 12726 2241 436
As you can see, there's not much in it for low counts, but the time
for the tail recursive template increases exponentially, the
non-tail-recursive template increases more than the divide and conquer
template, which stays roughly the same throughout.
Of course the real situations where you'd want to nest a string within
even 50 foo elements are pretty far and few between, but it proves
your point.
That's the last time I let David C. indoctrinate me ;)
Cheers,
Jeni
---
Jeni Tennison
http://www.jenitennison.com/
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list